Skip to main content
SpringerLink
Log in

Proportionate flow-shop scheduling with rejection

  • General Paper
  • Published:
Journal of the Operational Research Society

Abstract

In many heavily loaded manufacturing systems, managers routinely make use of outsourcing options in order to maintain reasonable Quality of Service for customers. Thus, there is a strong need to provide tools for managers to economically coordinate sourcing and scheduling decisions. Our main aim is to provide such tools for an important set of flow-shop scheduling problems where rejection (outsourcing) is allowed and processing times are machine-independent. Our scheduling problems are essentially bicriteria problems, which combine a scheduling objective and the total outsourcing cost. We study several problems which differ according to the scheduling criterion considered. Moreover, each problem is divided into four different variations depending on the way the two criteria are dealt with. For example, in one variation the two criteria are aggregated into a single objective function; in two other variations the aim consists of minimizing one criterion subject to ensuring that the value of the other criterion will not exceed a predefined threshold. From a theoretical point of view, a computational complexity classification is provided for all variations of the problems under consideration. Moreover, optimization algorithms have been constructed to solve all problem variations, and approximation schemes have been developed for solving hard variations. Those schemes enable managers to solve large instances of hard variations while controlling the maximal gap between the obtained solution and the (unknown) optimal solution.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  • Bartal Y, Leonardi S, Marchetti-Spaccamela A, Sgall J and Stougie L (2000). Multiprocessor scheduling with rejection. In: Seventh ACM-SIAM Symposium on Discrete Algorithms. Atlanta, Georgia, pp 95–103.

  • Cao Z, Wang A, Zhang Y and Liu S (2006). On Several Scheduling Problems with Rejection or Discretely Compressible Processing Times. Lecture Notes in Computer Science, Vol. 3959, Springer-Verlag: Berlin, Heidelberg, pp 90–98.

  • Cao Z and Yang X (2009). A PTAS for parallel batch scheduling with rejection and dynamic job arrivals. Theoretical Computer Science 410 (27): 2732–2745.

    Article  Google Scholar 

  • Cao Z and Zhang Y (2007). Scheduling with rejection and non-identical job arrivals. Journal of Systems Science and Complexity 20 (4): 529–535.

    Article  Google Scholar 

  • Cesaret B, Oğuz C and Salman FS (2012). A Tabu search algorithm for order acceptance and scheduling. Computers and Operations Research 39 (6): 1197–1205.

    Article  Google Scholar 

  • Cheng Y and Sun S (2007). Scheduling linear deteriorating jobs with rejection on a single machine. European Journal of Operational Research 194 (1): 18–27.

    Article  Google Scholar 

  • Choi BC and Chung J (2011). Two-machine flow shop scheduling problem with an outsourcing option. European Journal of Operational Research 213 (1): 66–72.

    Article  Google Scholar 

  • Choi BC, Yoon SH and Chung SJ (2007). Minimizing maximum completion time in a proportionate flow shop with one machine of different speed. European Journal of Operational Research 176 (2): 964–974.

    Article  Google Scholar 

  • Chubanov S, Kovalyov M and Pesch E (2006). An FPTAS for a single-item capacity economic lot-sizing problem with monotone cost structure. Mathematical Programming, Series A 106 (3): 453–466.

    Article  Google Scholar 

  • De P, Ghosh JB and Wells CE (1991). Optimal delivery time quotation and order Sequencing. Decision Sciences 22 (2): 379–390.

    Article  Google Scholar 

  • Dreyfus SE and Bellman RE (1962). Applied Dynamic Programming. Princeton University Press: Santa Monica.

    Google Scholar 

  • Engels DW, Karger DR, Kolliopoulos SG, Segupta S, Uma RN and Wein J (2003). Techniques for scheduling with rejection. Journal of Algorithms 49 (1): 175–191.

    Article  Google Scholar 

  • Gao Q and Lu X (2014). Two-machine flow shop scheduling with individual operation's rejection. Asia-Pacific Journal of Operational Research 31 (1): 1–13.

    Google Scholar 

  • Guerrero HH and Kern GM (1988). How to more effectively accept and refuse orders. Production and Inventory Management 29 (4): 59–63.

    Google Scholar 

  • Halman N, Klabjan D, Li CL, Orlin J and Simchi-Levi D (2014). Fully polynomial time approximation schemes for stochastic dynamic programming. SIAM Journal of Discrete Mathematics 28 (4): 1725–1796.

    Article  Google Scholar 

  • Ibarra O and Kim C (1975). Fast approximation algorithms for the sum of subsets problems. Journal of the ACM 22 (4): 463–468.

    Article  Google Scholar 

  • Józefowska J, Jurisch B and Kubiak W (1994). Scheduling shops to minimize the weighted number of late jobs. Operations Research Letters 16 (5): 277–283.

    Article  Google Scholar 

  • Karp RM (1972). Reducibility among combinatorial problems. In: Miller RE and Thatcher JW (eds). Complexity of Computer Computations. Plenum Press: New York, pp 85–103.

    Chapter  Google Scholar 

  • Kellerer H and Pferschy U (1999). A new fully polynomial approximation scheme for the Knapsack problem. Journal of Combinatorial Optimization 3 (1): 59–71.

    Article  Google Scholar 

  • Khuller S and Mestre J (2008). An optimal incremental algorithm for minimizing lateness with rejection. Lecture Notes in Computer Science 5193: 601–610.

    Article  Google Scholar 

  • Lawler EL (1977). Fast approximation algorithms for knapsack problems. In: Proceedings of the 18th Annual Symposium on Foundation of Computer Science, IEEE Computer Society, Long Beach, CA, pp 206–213.

  • Lee K and Choi BC (2011). Two-stage production scheduling with an outsourcing option. European Journal of Operational Research 213 (3): 489–497.

    Article  Google Scholar 

  • Lei D and Guo X (2015). A parallel neighborhood search for order acceptance and scheduling in flow shop environment. International Journal of Production Economics 165: 12–18.

    Article  Google Scholar 

  • Leung JYT (2004). Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press: New York.

    Google Scholar 

  • Magazine MJ and Oguz O (1981). A fully polynomial approximation algorithm for the 0–1 Knapsack problem. European Journal of Operational Research 8 (3): 270–273.

    Article  Google Scholar 

  • McGovern G and Quelch J (2005). Outsourcing marketing. Harvard Business Review 83: 2–3.

    Google Scholar 

  • Panwalker SS, Dudek RA and Smith ML (1973). Sequencing research and the industrial problem. In: Elmaghraby SE (ed). Symposium on the Theory of Scheduling and its Applications. Springer: Berlin, pp 29–38.

    Chapter  Google Scholar 

  • Pinedo M (2008). Scheduling: Theory, Algorithms and Systems. 3rd edn, Prentice-Hall: New Jersey.

    Google Scholar 

  • Sahni S (1976). Algorithms for scheduling independent tasks. Journal of the ACM 23 (1): 116–127.

    Article  Google Scholar 

  • Sengupta S (2003). Algorithms and approximation schemes for minimum lateness/ tardiness scheduling with rejection. Lecture Notes in Computer Science 2748: 79–90.

    Article  Google Scholar 

  • Shabtay D and Gaspar N (2012). Two-machine flow-shop with rejection. Computers and Operations Research 39 (5): 1087–1096.

    Article  Google Scholar 

  • Shabtay D, Gaspar N and Kaspi M (2013). A survey on scheduling problems with rejection. Journal of Scheduling 16 (1): 3–28.

    Article  Google Scholar 

  • Shabtay D, Gaspar N and Yedidsion L (2012). A bicriteria approach to scheduling a single machine with job rejection and positional penalties. Journal of Combinatorial Optimization 23 (4): 395–424.

    Article  Google Scholar 

  • Shakhlevich N, Hoogeveen H and Pinedo M (1998). Minimizing total weighted completion time in a proportionate flow shop. Journal of Scheduling 1 (3): 157–168.

    Article  Google Scholar 

  • Slotnick SA (2011). Order acceptance and scheduling: A taxonomy and review. European Journal of Operational Research 212 (1): 1–11.

    Article  Google Scholar 

  • T’kindt V and Billaut JC (2006). Multicriteria Scheduling: Theory, Models and Algorithms. 2nd edn, Springer: Berlin.

    Google Scholar 

  • T’kindt V and Croce FD (2012). A note on ‘two-machine flow-shop scheduling with rejection’ and its link with flow-shop scheduling and common due date assignment. Computers & Operations Research 39 (12): 3244–3246.

    Article  Google Scholar 

  • T’kindt V, Della Croce F and Bouquard JL (2007). Enumeration of pareto optima for a flowshop scheduling problem with two criteria. INFORMS Journal of Computing 19 (1): 64–72.

    Article  Google Scholar 

  • Wang XL, Xie XZ and Cheng TCE (2013a). A modified artificial bee colony algorithm for order acceptance in two-machine flow shops. International Journal of Production Economics 141 (1): 14–23.

    Article  Google Scholar 

  • Wang XL, Xie XZ and Cheng TCE (2013b). Order acceptance and scheduling in a two-machine flowshop. International Journal of Production Economics 141 (2): 366–376.

    Article  Google Scholar 

  • Woeginger GJ (2000). When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? INFORMS Journal of Computing 12 (1): 57–74.

    Article  Google Scholar 

  • Xiao YY, Zhang RQ, Zhao QH and Kaku I (2012). Permutation flow shop scheduling with order acceptance and weighted tardiness. Applied Mathematics and Computation 218 (15): 7911–7926.

    Article  Google Scholar 

  • Zhang L, Lu L and Li S (2015). New results on two-machine flow-shop scheduling with rejection, to appear in. Journal of Combinatorial Optimization doi:10.1007/s10878-015-9836-3.

  • Zhang Y, Ren J and Wang C (2009). Scheduling with rejection to minimize the makespan. Lecture Notes in Computer Science 5573: 411–420.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Ben-Gurion University of the Negev, Beer-Sheva, Israel

    Dvir Shabtay

  2. The University of Sydney, Sydney, Australia

    Daniel Oron

Authors
  1. Dvir Shabtay
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Daniel Oron
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Daniel Oron.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Shabtay, D., Oron, D. Proportionate flow-shop scheduling with rejection. J Oper Res Soc 67, 752–769 (2016). https://doi.org/10.1057/jors.2015.95

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2015.95

Keywords

Search

Navigation