Scheduling a proportionate flow shop of batching machines
Tóm tắt
In this paper we study a proportionate flow shop of batching machines with release dates and a fixed number
$$m \ge 2$$
of machines. The scheduling problem has so far barely received any attention in the literature, but recently its importance has increased significantly, due to applications in the industrial scaling of modern bio-medicine production processes. We show that for any fixed number of machines, the makespan and the sum of completion times can be minimized in polynomial time. Furthermore, we show that the obtained algorithm can also be used to minimize the weighted total completion time, maximum lateness, total tardiness and (weighted) number of late jobs in polynomial time if all release dates are 0. Previously, polynomial time algorithms have only been known for two machines.
Tài liệu tham khảo
Ackermann, H., Heydrich, S., & Weiß, C. (2020+). Analyzing and optimizing the throughput of a pharmaceutical production process. In Operations research proceedings 2019, Springer, accepted.
Ahmadi, J. H., Ahmadi, R. H., Dasu, S., & Tang, C. S. (1992). Batching and scheduling jobs on batch and discrete processors. Operations Research, 40(4), 750–763.
Baptiste, P. (2000). Batching identical jobs. Mathematical Methods of Operations Research, 52(3), 355–367.
Brucker, P. (2007). Scheduling Algorithms (5th ed.). Berlin: Springer.
Brucker, P., & Knust, S. (2009). Complexity results for scheduling problems. http://www.informatik.uni-osnabrueck.de/knust/class/. Accessed on September 11, 2018.
Brucker, P., & Shakhlevich, N. V. (2011). A polynomial-time algorithm for a flow-shop batching problem with equal-length operations. Journal of Scheduling, 14(4), 371–389.
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.
Chen, Z., Zheng, X., Zhou, S., Liu, C., & Chen, H. (2019). Quantum-inspired ant colony optimisation algorithm for a two-stage permutation flow shop with batch processing machines. International Journal of Production Research.
Condotta, A., Knust, S., & Shakhlevich, N. V. (2010). Parallel batch scheduling of equal-length jobs with release and due dates. Journal of Scheduling, 13(5), 463–477.
Diessel, E., & Ackermann, H. (2019). Domino sequencing: Scheduling with state-based sequence-dependent setup times. Operations Research Letters, 47(4), 274–280.
Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117–129.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. In P. L. Hammer, E. L. Johnson, & B. H. Korte (Eds.), Discrete optimization II, annals of discrete mathematics (Vol. 5, pp. 287–326). Amsterdam: Elsevier.
Hertrich, C. (2018). Scheduling a proportionate flow shop of batching machines. Master thesis, Technische Universität Kaiserslautern. http://nbn-resolving.de/urn:nbn:de:hbz:386-kluedo-54968.
Hochbaum, D. S., & Shamir, R. (1990). Minimizing the number of tardy job units under release time constraints. Discrete Applied Mathematics, 28(1), 45–57.
Hochbaum, D. S., & Shamir, R. (1991). Strongly polynomial algorithms for the high multiplicity scheduling problem. Operations Research, 39(4), 648–653.
Ikura, Y., & Gimple, M. (1986). Efficient scheduling algorithms for a single batch processing machine. Operations Research Letters, 5(2), 61–65.
Johnson, S. M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61–68.
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, D., Meng, X., Liang, Q., & Zhao, J. (2015). A heuristic-search genetic algorithm for multi-stage hybrid flow shop scheduling with single processing machines and batch processing machines. Journal of Intelligent Manufacturing, 26(5), 873–890.
Li, F., Zhang, Y., Wei, H., & Lai, X. (2019). Integrated problem of soaking pit heating and hot rolling scheduling in steel plants. Computers & Operations Research, 108, 238–246.
Mnich, M., & van Bevern, R. (2018). Parameterized complexity of machine scheduling: 15 open problems. Computers & Operations Research, 100, 254–261.
Mnich, M., & Wiese, A. (2015). Scheduling and fixed-parameter tractability. Mathematical Programming, 154(1), 533–562.
Ng, C. T., & Kovalyov, M. Y. (2007). Batching and scheduling in a multi-machine flow shop. Journal of Scheduling, 10(6), 353–364.
Panwalkar, S. S., Smith, M. L., & Koulamas, C. (2013). Review of the ordered and proportionate flow shop scheduling research. Naval Research Logistics (NRL), 60(1), 46–55.
Passchyn, W., & Spieksma, F. C. R. (2019). Scheduling parallel batching machines in a sequence. Journal of Scheduling, 22(3), 335–357.
Potts, C. N., Strusevich, V. A., & Tautenhahn, T. (2001). Scheduling batches with simultaneous job processing for two-machine shop problems. Journal of Scheduling, 4(1), 25–51.
Rachamadugu, R. V., Vepsalainen, A., & Morton, T. E. (1982). Scheduling in proportionate flowshops. Tech. Rep. CMU-RI-TR-83-10, Carnegie Mellon University, Pittsburgh, PA.
Sung, C. S., & Kim, Y. H. (2003). Minimizing due date related performance measures on two batch processing machines. European Journal of Operational Research, 147(3), 644–656.
Sung, C. S., & Yoon, S. H. (1997). Minimizing maximum completion time in a two-batch-processing-machine flowshop with dynamic arrivals allowed. Engineering Optimization, 28(3), 231–243.
Sung, C. S., Kim, Y. H., & Yoon, S. H. (2000). A problem reduction and decomposition approach for scheduling for a flowshop of batch processing machines. European Journal of Operational Research, 121(1), 179–192.
Tan, Y., Mönch, L., & Fowler, J. W. (2018). A hybrid scheduling approach for a two-stage flexible flow shop with batch processing machines. Journal of Scheduling, 21(2), 209–226.
Weiß, C., Knust, S., Shakhlevich, N., & Waldherr, S. (2016). The assignment problem with nearly monge arrays and incompatible partner indices. Discrete Applied Mathematics, 211, 183–203.
Zhou, S., Li, X., Chen, H., & Guo, C. (2016). Minimizing makespan in a no-wait flowshop with two batch processing machines using estimation of distribution algorithm. International Journal of Production Research, 54(16), 4919–4937.