nach oben

Journal of Scheduling

Erschienen in:

01.02.2013

A survey on offline scheduling with rejection

verfasst von: Dvir Shabtay, Nufar Gaspar, Moshe Kaspi

Erschienen in: Journal of Scheduling | Ausgabe 1/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Journal of Scheduling (2013)

Nächster Artikel Scheduling satellite launch missions: an MILP approach

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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.

Titel: A survey on offline scheduling with rejection
verfasst von: Dvir Shabtay
Nufar Gaspar
Moshe Kaspi
Publikationsdatum: 01.02.2013
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 1/2013
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-012-0303-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2013

Flexible weekly tour scheduling for postal service workers using a branch and price

Fast minimum float computation in activity networks under interval uncertainty

Scheduling satellite launch missions: an MILP approach

Real-time integrated prefetching and caching

Journal of Scheduling (2013)

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

Premium Partner