nach oben

Journal of Scheduling

Erschienen in:

11.09.2019

Mixed batch scheduling on identical machines

verfasst von: Jun-Qiang Wang, Guo-Qiang Fan, Zhixin Liu

Erschienen in: Journal of Scheduling | Ausgabe 4/2020

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This paper studies a new mixed batch scheduling problem that arises in vacuum heat treatment. A mixed batch machine can process at most a given number of jobs simultaneously. The processing time of a batch is the weighted sum of the maximum processing time and the total processing time of jobs in the batch. The objective is to minimize the makespan. We first prove that the problem on a single machine can be solved in polynomial time, while the problem on multiple identical machines is NP-hard. Then, we develop a pseudopolynomial time exact algorithm when the number of machines is fixed. Further, we analyze the worst-case performance ratio of a full batch longest processing time algorithm and design Algorithm LPT-Greedy with improved worst-case performance.

Vorheriger Artikel Interference aware scheduling of triple-crossover-cranes

Nächster Artikel Single-machine scheduling with multi-agents to minimize total weighted late work

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

Albers, S., & Brucker, P. (1993). The complexity of one-machine batching problems. Discrete Applied Mathematics, 47(2), 87–107.

Aloulou, M. A., Bouzaiene, A., Dridi, N., & Vanderpooten, D. (2014). A bicriteria two-machine flow-shop serial-batching scheduling problem with bounded batch size. Journal of Scheduling, 17(1), 17–29.

Baptiste, P. (2000). Batching identical jobs. Mathematical Methods of Operations Research, 52(3), 355–367.

Barketau, M. S., Cheng, T. C. E., Ng, C. T., Kotov, V., & Kovalyov, M. Y. (2008). Batch scheduling of step deteriorating jobs. Journal of Scheduling, 11(1), 17–28.

Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M. Y., Potts, C. N., Tautenhahn, T., et al. (1998). Scheduling a batching machine. Journal of Scheduling, 1(1), 31–54.

Chandru, V., Lee, C. Y., & Uzsoy, R. (1993a). Minimizing total completion time on a batch processing machine with job families. Operations Research Letters, 13(2), 61–65.

Chandru, V., Lee, C. Y., & Uzsoy, R. (1993b). Minimizing total completion time on batch processing machines. International Journal of Production Research, 31(9), 2097–2121.

Cheng, T. C. E., Chen, Z. L., Kovalyov, M. Y., & Lin, B. M. T. (1996). Parallel-machine batching and scheduling to minimize total completion time. IIE Transactions, 28(11), 953–956.

Cheng, T. C. E., & Kovalyov, M. Y. (2001). Single machine batch scheduling with sequential job processing. IIE Transactions, 33(5), 413–420.

Coffman, E. G., Yannakakis, M., Magazine, M. J., & Santos, C. (1990). Batch sizing and job sequencing on a single machine. Annals of Operations Research, 26(1), 135–147.

Dang, C., & Kang, L. (2004). Batch-processing scheduling with setup times. Journal of Combinatorial Optimization, 8(2), 137–146.

Deng, X., Feng, H., Li, G., & Liu, G. (2002). A PTAS for minimizing total completion time of bounded batch scheduling. International Journal of Foundations of Computer Science, 13(06), 817–827.

Gao, Y., Yuan, J. J., & Wei, Z. (2019). Unbounded parallel-batch scheduling with drop-line tasks. Journal of Scheduling, 22(4), 449–463.

Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326.

He, C., Lin, H., & Lin, Y. (2015). Bounded serial-batching scheduling for minimizing maximum lateness and makespan. Discrete Optimization, 16, 70–75.

Hochbaum, D. S., & Landy, D. (1997). Scheduling semiconductor burn-in operations to minimize total flowtime. Operations Research, 45(6), 874–885.

Ikura, Y., & Gimple, M. (1986). Efficient scheduling algorithms for a single batch processing machine. Operations Research Letters, 5(2), 61–65.

Kovalyov, M. Y., Oulamara, A., & Soukhal, A. (2015). Two-agent scheduling with agent specific batches on an unbounded serial batching machine. Journal of Scheduling, 18(4), 423–434.

Lee, C. Y. (1999). Minimizing makespan on a single batch processing machine with dynamic job arrivals. International Journal of Production Research, 37(1), 219–236.

Lee, C. Y., Uzsoy, R., & Martin-Vega, L. A. (1992). Efficient algorithms for scheduling semiconductor burn-in operations. Operations Research, 40(4), 764–775.

Li, S. S., & Zhang, Y. Z. (2014). Serial batch scheduling on uniform parallel machines to minimize total completion time. Information Processing Letters, 114(12), 692–695.

Liu, L., Wang, J., & Zhang, F. (2009). Scheduling jobs on parallel batch processing machines. In ISECS International colloquium on computing, communication, control, and management. CCCM 2009 (Vol. 1, pp. 78–81). IEEE.

Liu, L. L., Ng, C. T., & Cheng, T. C. E. (2010). On the complexity of bi-criteria scheduling on a single batch processing machine. Journal of scheduling, 13(6), 629–638.

Liu, Z., Lu, L., & Qi, X. (2018). Cost allocation in rescheduling with machine unavailable period. European Journal of Operational Research, 266(1), 16–28.

Liu, Z., & Ro, Y. K. (2014). Rescheduling for machine disruption to minimize makespan and maximum lateness. Journal of Scheduling, 17(4), 339–352.

Mathirajan, M., & Sivakumar, A. I. (2006). A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor. The International Journal of Advanced Manufacturing Technology, 29(9–10), 990–1001.

Miao, C. X., Xia, Y. J., Zhang, Y. Z., & Zou, J. (2013). Batch scheduling with deteriorating jobs to minimize the total completion time. Journal of the Operations Research Society of China, 1(3), 377–383.

Nong, Q. Q., Fan, G. Q., & Fang, Q. Z. (2017). A coordination mechanism for a scheduling game with parallel-batching machines. Journal of Combinatorial Optimization, 33(2), 567–579.

Poon, C. K., & Yu, W. (2004). On minimizing total completion time in batch machine scheduling. International Journal of Foundations of Computer Science, 15(04), 593–607.

Potts, C. N., & Kovalyov, M. Y. (2000). Scheduling with batching: A review. European Journal of Operational Research, 120(2), 228–249.

Potts, C. N., & Van Wassenhove, L. N. (1992). Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity. Journal of the Operational Research Society, 43(5), 395–406.

Shabtay, D. (2014). The single machine serial batch scheduling problem with rejection to minimize total completion time and total rejection cost. European Journal of Operational Research, 233(1), 64–74.

Tang, L., Liu, J., Rong, A., & Yang, Z. (2001). A review of planning and scheduling systems and methods for integrated steel production. European Journal of Operational Research, 133(1), 1–20.

Tang, L., & Wang, X. (2010). A scatter search algorithm for a multistage production scheduling problem with blocking and semi-continuous batching machine. IEEE Transactions on Control Systems Technology, 19(5), 976–989.

Tang, L., & Zhao, Y. (2008). Scheduling a single semi-continuous batching machine. Omega, 36(6), 992–1004.

Uzsoy, R. (1994). Scheduling a single batch processing machine with non-identical job sizes. International Journal of Production Research, 32(7), 1615–1635.

Uzsoy, R. (1995). Scheduling batch processing machines with incompatible job families. International Journal of Production Research, 33(10), 2685–2708.

Wang, J. Q., Fan, G. Q., Zhang, Y., Zhang, C. W., & Leung, J. Y. T. (2017). Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes. European Journal of Operational Research, 258(2), 478–490.

Wang, J. Q., & Leung, J. Y. T. (2014). Scheduling jobs with equal-processing-time on parallel machines with non-identical capacities to minimize makespan. International Journal of Production Economics, 156, 325–331.

Webster, S., & Baker, K. R. (1995). Scheduling groups of jobs on a single machine. Operations Research, 43(4), 692–703.

Yuan, J. J., Lin, Y. X., Cheng, T. C. E., & Ng, C. T. (2007). Single machine serial-batching scheduling problem with a common batch size to minimize total weighted completion time. International Journal of Production Economics, 105(2), 402–406.

Zhang, G., Cai, X., Lee, C. Y., & Wong, C. K. (2001). Minimizing makespan on a single batch processing machine with nonidentical job sizes. Naval Research Logistics, 48(3), 226–240.

Titel: Mixed batch scheduling on identical machines
verfasst von: Jun-Qiang Wang
Guo-Qiang Fan
Zhixin Liu
Publikationsdatum: 11.09.2019
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 4/2020
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-019-00623-9

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 4/2020

Interference aware scheduling of triple-crossover-cranes

Benders decomposition for the mixed no-idle permutation flowshop scheduling problem

An Efficient Filtering Algorithm for the Unary Resource Constraint with Transition Times and Optional Activities

On the exact solution of a large class of parallel machine scheduling problems

Interruptible algorithms for multiproblem solving

Single-machine scheduling with multi-agents to minimize total weighted late work