Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Scheduling
Published in: Journal of Scheduling 1/2013

01-02-2013

A survey on offline scheduling with rejection

Authors: Dvir Shabtay, Nufar Gaspar, Moshe Kaspi

Published in: Journal of Scheduling | Issue 1/2013

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In classical deterministic scheduling problems, it is assumed that all jobs have to be processed. However, in many practical cases, mostly in highly loaded make-to-order production systems, accepting all jobs may cause a delay in the completion of orders which in turn may lead to high inventory and tardiness costs. Thus, in such systems, the firm may wish to reject the processing of some jobs by either outsourcing them or rejecting them altogether. The field of scheduling with rejection provides schemes for coordinated sales and production decisions by grouping them into a single model. Since scheduling problems with rejection are very interesting both from a practical and a theoretical point of view, they have received a great deal of attention from researchers over the last decade. The purpose of this survey is to offer a unified framework for offline scheduling with rejection by presenting an up-to-date survey of the results in this field. Moreover, we highlight the close connection between scheduling with rejection and other fields of research such as scheduling with controllable processing times and scheduling with due date assignment, and include some new results which we obtained for open problems.
previous article Journal of Scheduling (2013)
next article Scheduling satellite launch missions: an MILP approach

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Literature
Alidaee, B., & Ahmadian, A. (1993). Two parallel machine sequencing problems involving controllable job processing times. European Journal of Operational Research, 70(3), 335–341.CrossRef
Angel, E., Bampis, E., & Kononov, A. (2001). A FPTAS for approximating the unrelated parallel machines scheduling problem with costs. Lecture Notes in Computer Science, 2161, 194–205.CrossRef
Bechman, A., Janiak, A., & Kovalyov, M. Y. (2002). Minimizing the total weighted completion time of deteriorating jobs. Information Processing Letters, 81(2), 81–84.CrossRef
Bartal, Y., Leonardi, S., Marchetti-Spaccamela, A., Sgall, J., & Stougie, L. (2000). Multiprocessor scheduling with rejection. SIAM Journal of Discrete Mathematics, 13(1), 64–78.CrossRef
Bilgintürk, Z., Oğuz, C., & Salman, S. (2007). Order acceptance and scheduling decisions in make-to-order systems. In 5th Multidisciplinary International Scheduling Conference: Theory and Applications, Paris, France.
Cao, Z., Wang, Z., Zhang, Y., & Liu, S. (2006). On several scheduling problems with rejection or discretely compressible processing times. Lecture Notes in Computer Science, 3959, 90–98.CrossRef
Cao, Z., & Yang, X. (2009). A PTAS for parallel batch scheduling with rejection and dynamic job arrivals. Theoretical Computer Science, 410, 2732–2745.CrossRef
Cao, Z., & Zhang, Y. (2007). Scheduling with rejection and non-identical job arrivals. Journal of Systems Science and Complexity, 20, 529–535.CrossRef
Cesaret, B., Oğuz, C., & Salman, F. S. (2012). A tabu search algorithm for order acceptance and scheduling. Computers and Operations Research, 39(6), 1197–1205.CrossRef
Cheng, Y., & Sun, S. (2009). Scheduling linear deteriorating jobs with rejection on a single machine. European Journal of Operational Research, 194(1), 18–27.
Choi, B. C., Yoon, S. H., & Chung, S. J. (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.CrossRef
Choi, B. C., & Chung, J. (2011). Two-machne flow shop schedulng problem with an outsourcing option. European Journal of Operational Research, 213, 66–72.CrossRef
Chudak, F. (1999). A min-sum 1.5-approximation algorithm for scheduling unrelated parallel machines. Journal of Scheduling, 2(2), 73–77.CrossRef
De, P., Ghosh, J. B., & Wells, C. E. (1991). Optimal delivery time quotation and order sequencing. Decision Sciences, 22(2), 379–390.
Engels, D. W., Karger, D. R., Kolliopoulos, S. G., Sengupta, S., Uma, R. N., & Wein, J. (2003). Techniques for scheduling with rejection. Journal of Algorithms, 49(1), 175–191.CrossRef
Gaspar, N., & Shabtay, D. (2010). Various special cases of the multiple-machine flow-shop scheduling problem with rejection. Working Paper.
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of \(\cal NP\) -completeness. San Francisco: Freeman.
Ghosh, J. B. (1997). Job selection in a heavily loaded shop. Computers and Operations Research, 24(2), 141–145.CrossRef
Gonzalez, T., & Sahni, S. (1976). Open shop scheduling to minimize finish time. Journal of Association of Computing Machinery, 23(4), 665–679.CrossRef
Gordon, V., Proth, J. M., & Chu, C. B. (2002). A survey of the state-of-the-art of common due date assignment and scheduling research. European Journal of Operational Research, 139(1), 1–25.
Gordon, V., Proth, J. M., & Chu, C. B. (2002). Due date assignment and scheduling: SLK, TWK and other due date assignment models. Production Planning and Control, 13(2), 117–132.CrossRef
Gordon, V., Proth, J. M., & Strusevich, V. A. (2004). Scheduling with due date assignment. In J. Y.-T. Leung (Ed.), Handbook of scheduling (pp. 21-1-21-22). Boca Raton, FL: CRC Press.
Graham, R. L., Lawler, E. L., & Lenstra, J. K. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 4, 287–326.CrossRef
Guerrero, H. H., & Kern, G. M. (1988). How to more effectively accept and refuse orders. Production and Inventory Management, 29(4), 59–63.
Gurel, S., & Akturk, M. S. (2007). Scheduling parallel CNC machines with time/cost trade-off considerations. Computers and Operations Research, 34(9), 2774–2789.CrossRef
Hoogeveen, H., Skutella, M., & Woeginger, G. J. (2003). Preemptive scheduling with rejection. Mathematical Programming, 94(3), 361–374.CrossRef
Hoogeveen, H. (2005). Multicriteria scheduling. European Journal of Operational Research, 167, 592–623.CrossRef
Jansen, K., & Porkolab, L. (1999). Improved approximation schemes for scheduling unrelated parallel machines. In STOC ’99 Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, Atlanta (pp. 408–417).
Józefowska, J., Jurisch, B., & Kubiak, W. (1994). Scheduling shops to minimize the weighted number of late jobs. Operations Research Letters, 16, 277–283.CrossRef
Kaminsky, P., & Hochbaum, D. (2004). Due date quotation models and algorithms. In J. Y.-T. Leung (Ed.), Handbook of scheduling (pp. 20-1–20-22). Boca Raton, FL: CRC Press.
Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of computer computations (pp. 85–103). New York: Plenum Press.
Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack problems. Berlin: Springer.CrossRef
Khuller, S., & Mestre, J. (2008). An optimal incremental algorithm for minimizing lateness with rejection. Lecture Notes in Computer Science, 5193, 601–610.CrossRef
Koulamas, C. (2010). A faster algorithm for a due date assignment problem with tardy jobs. Operations Research Letters, 38(2), 127–128.CrossRef
Lawler, E. L., & Moore, J. M. (1969). A functional equation and its application to resource allocation and sequencing problems. Management Science, 16(1), 77–84.CrossRef
Lawler, E. L. (1973). Optimal sequencing of a single machine subject to precedence constraints. Operations Research, 26, 544–546.
Lawler, E. L., & Lenstra, J. K. (1982). Recent developments in deterministic sequencing and scheduling: A survey. In J. K. Lenstra & A. H. G. Rinnooy Kan (Eds.), Deterministic and stochastic scheduling (pp. 35–73). Dordrecht: Dempster, Reidel.
Leung, J. Y. T., & Li, C. L. (2008). Scheduling with processing time restriction: A survey. International Journal of Production Economics, 116(2), 251–262.CrossRef
Li, X., & Feng, H. (2010). Minimize the sum of total completion time and total rejection penalties on a single batching machine. In Procedding of the International Conference on Information, Engineering (pp. 200–202).
Lin, J. H., & Vitter, J. S. (1992). \(\varepsilon \)-Approximation algorithms with minimum packing constraint violation. In STOC ’92 Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (pp. 771–782).
Li, S., & Yuan, J. (2010). Parallel-machine scheduling with deteriorating jobs and rejection. Theoretical Computer Science, 411, 3642–3650.CrossRef
Lu, L., Cheng, T. C. E., Yuan, J., & Zhang, L. (2009). Bounded single-machine parallel-batch scheduling with release dates and rejection. Computers and Operations Research, 36(10), 2748–2751.CrossRef
Lu, L., Zhang, L., & Yuan, J. (2008). The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan. Theoretical Computer Science, 396, 283–289.CrossRef
Miao, C., Zhang, Y., & Wang, C. (2010). Bounded parallel-batch scheduling on unrelated parallel machines. Lecture Notes in Computer Science, 6124, 220–228.CrossRef
Moghaddam, A., Yalaoui, F., Amodeo, L., Karimi, B., & Jolai, F. (2010). Developing a technique for a bi-objective scheduling model with rejection by simulated annealing. In MOSIM’10, Proceedings of the Eight International Conference of Modeling and Simulation, Hammamet.
Mosheiov, G. (2003). Scheduling unit processing time jobs on an \(m\)-machine flow shop. Journal of the Operational Research Society, 54(4), 437–441.
Mosheiov, G., & Oron, D. (2005). A note on flow-shop and job-shop batch scheduling with identical processing-time jobs. European Journal of Operational Research, 161(1), 285–291.CrossRef
Mosheiov, G., & Sarig, A. (2009). Scheduling and due-date assignment problems with job rejection. Foundations of Computing and Decision Sciences, 34(3), 193–208.
McGovern, G., & Quelch, J. (2005). Outsourcing marketing. Harvard Business Review, 83, 2–3.
Nobibon, F. T., & Leus, R. (2011). Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment. Computers and Operations Research, 38(10), 367–378.CrossRef
Oğuz, C., Salman, S., & Bilgintürk, Z. (2010). Order acceptance and scheduling decisions in make-to-order systems. International Journal of Production Economics, 125(1), 200–211.CrossRef
Orlin, J. B., Schulz, A. S., & Sengupta, S. (2000). \(\varepsilon \)-Optimization schemes and L-Bit precision: Alternative perspectives in combinatorial optimization. In STOC ’00 Proceedings of the Thirty-Two Annual ACM Symposium on Theory of Computing.
Panwalker, S. S., Dudek, R. A., & Smith, M. L. (1973). Sequencing research and the industrial problem. In S. E. Elmaghraby (Ed.), Symposium on the theory of scheduling and its applications (pp. 29–38). Berlin: Springer.CrossRef
Papadimitriou, C. H., & Yannakakis, M. (2000). On the approximability of trade-offs and optimal access of web sources. In Proceedings 41th Annual IEEE Symposium on Foundations of Computer Science, Redondo Beach, CA, USA (pp. 86–92).
Phillips, C. A., Uma, R. N., & Wein, J. (2000). Off-line admission control for general scheduling problems. Journal of Scheduling, 3, 365–381.CrossRef
Pinedo, M. (2008). Scheduling: Theory, algorithms and systems (3rd ed.). Upper Saddle River, NJ: Prentice-Hall.
Rom, W. O., & Slotnick, S. A. (2009). Order acceptance using genetic algorithms. Computers and Operations Research, 36(5), 1758– 1767.
Rothkopf, M. H. (1966). Scheduling independent tasks on parallel processors. Management Science, 12(5), 437–447.CrossRef
Sahni, S. (1976). Algorithms for scheduling independent tasks. Journal of the ACM, 23(1), 116–127.CrossRef
Schulz, A. S., & Skutella, M. (1997). Random-based scheduling: New approximations and LP lower bounds. Lecture Notes in Computer Science, 1269, 119–133.CrossRef
Schulz, A. S., & Skutella, M. (1997). Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria. Lecture Notes in Computer Science, 1284, 416–429.CrossRef
Sengupta, S. (2003). Algorithms and approximation schemes for minimum lateness/tardiness scheduling with rejection. Lecture Notes in Computer Science, 2748, 79–90.CrossRef
Shabtay, D., & Steiner, G. (2006). Two due date assignment problems in scheduling a single machine. Operations Research Letters, 34(6), 683–691.CrossRef
Shabtay, D., & Steiner, G. (2007). A survey of scheduling with controllable processing times. Discrete Applied Mathematics, 155(13), 1643–1666.CrossRef
Shabtay, D., Gaspar, N., & Yedidsion, L. (2012). A bicriteria approach to scheduling a single machine with rejection and positional penalties. Journal of Combinatorial Optimization, 23(4), 395–424.
Shabtay, D., & Gaspar, N. (2012). Two-machine flow-shop with rejection. Computers and Operations Research, 39(5), 1087–1096.CrossRef
Shakhlevich, N., Hoogeveen, H., & Pinedo, M. (1998). Minimizing total weighted completion time in a proportionate flow shop. Journal of Scheduling, 1(3), 157–168.CrossRef
Shmoys, D. B., & Tardos, E. (1993). An approximation algorithm for the generalized assignment problem. Mathematical Programming, 62, 461–474.CrossRef
Slotnick, S. A., & Morton, T. E. (1996). Selecting jobs for a heavily loaded shop with lateness penalties. Computers and Operations Research, 23(2), 131–140.CrossRef
Slotnick, S. A., & Morton, T. E. (2007). Order acceptance with weighted tardiness. Computers and Operations Research, 34, 3029–3042.
Smith, W. E. (1956). Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3, 59–66.CrossRef
Steiner, G., & Zhang, R. (2011). Revised delivery-time quotation in scheduling with tardiness penalties. Operations Research, 59, 1504–1511.
T’kindt, V., & Billaut, J.-C. (2006). Multicriteria scheduling: Theory, models and algorithms (2nd ed.). Berlin: Springer.
T’kindt, V., & Della Croce, F. (2007). Enumeration of Pareto optima for a flowshop scheduling problem with two criteria. INFORMS Journal of Computing, 19(1), 64–72.CrossRef
Trick, M. A. (1994). Scheduling multiple variable-speed machines. Operations Research, 42(2), 234–248.CrossRef
Yang, B., & Geunes, J. (2007). A single resource scheduling problem with job-selection flexibility, tardiness costs and controllable processing times. Computers and Industrial Engineering, 53, 420–432.CrossRef
Zhang, S., Cao, Z., & Zhang Y. (2009a). Scheduling with rejection to minimize the total weighted completion time. In ISORA’09 (pp. 111–114).
Zhang, L., Lu, L., & Yuan, J. (2009b). Single machine scheduling with release dates and rejection. European Journal of Operational Research, 198(3), 975–978.
Zhang, L., Lu, L., & Yuan, J. (2010). Single-machine scheduling under the job rejection constraint. Theoretical Computer Science, 411, 1877–1882.CrossRef
Zhang, Y., Ren, J., & Wang, C. (2009c). Scheduling with rejection to minimize the makespan. Lecture Notes in Computer Science, 5573, 411–420.
Metadata
Title
A survey on offline scheduling with rejection
Authors
Dvir Shabtay
Nufar Gaspar
Moshe Kaspi
Publication date
01-02-2013
Publisher
Springer US
Published in
Journal of Scheduling / Issue 1/2013
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI
https://doi.org/10.1007/s10951-012-0303-z

Other articles of this Issue 1/2013

Journal of Scheduling 1/2013 Go to the issue

OriginalPaper

Fair online load balancing

OriginalPaper

Mixed-integer linear programming models for batch sterilization of packaged-foods plants

OriginalPaper

Single machine batch scheduling with release times and delivery costs

OriginalPaper

Online capacity maximization in wireless networks

OriginalPaper

Real-time integrated prefetching and caching

OriginalPaper

Exact algorithms for inventory constrained scheduling on a single machine

Premium Partner

    Image Credits