An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems
Tóm tắt
This paper presents the problem of batching and scheduling jobs belonging to incompatible job families on unrelated-parallel machines. More specifically, we investigate cost-efficient approaches for solving batching and scheduling problems concerning the desired lower bounds on batch sizes (
$${LB}_{b}$$
), which indirectly has a considerable impact on the production cost. Batch scheduling is a more realistic extension of the traditional group scheduling approach, in which the jobs belonging to a job family can be processed as multiple batches. The objective is to minimize the total weighted job completion time and tardiness subject to a machine- and sequence-dependent setup time, dynamic machine availability and job release times, customer segments and job priority, and different machine capability and eligibility criteria for processing. Solving this type of batch scheduling problem is a big challenge due to the high computational complexity incurred by both the sequencing assignment and batching composition. A machine learning random forest classification algorithm is used for the
$${LB}_{b}$$
determination. Then, an efficient mixed-integer linear programming model (MILP) is developed based on the flow conservation constraints of jobs on machines to reduce the computational complexity. By mapping the MILP model onto a network formulation, an equivalent integer set partitioning type formulation is developed for a branch-and-price optimization algorithm. Computational experiments carried out over different sets of instances, indicate the efficiency and effectiveness of the optimization algorithm, compared to the linear relaxation and relaxed MILP models. Regarding the only available benchmark in the literature, the optimization algorithm yields optimal solutions with affordable computational time.
Tài liệu tham khảo
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: Theory, algorithms, and applications. Prentice-Hall.
Arroyo, J. E. C., & Leung, J. Y. T. (2017). Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times. Computers & Operations Research, 78, 117–128.
Allahverdi, A., Ng, C. T., Cheng, T. C. E., & Kovalyov, M. Y. (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187, 985–1032.
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, 17–29.
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W., & Vance, P. H. (1998). Branch-and-price: Column generation for solving huge integer programs. Operations Research, 46(3), 316–329.
Bozorgirad, M. A., & Logendran, R. (2014). Developing tight lower bounds for hybrid flow shop scheduling problems. IIE annual conference proceedings. Montreal: Institute of industrial engineers.
Chen, Z. L., & Powell, W. B. (2003). Exact algorithms for scheduling multiple families of jobs on parallel machines. Naval Research Logistics (NRL), 50(7), 823–840.
Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101–111.
Desrochers, M., Desrosiers, J., & Solomon, M. (1992). A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40(2), 342–354.
Desrosiers, J., Dumas, Y., Solomon, M. M., & Soumis, F. (1995). Time constrained routing and scheduling. Handbooks in Operations Research and Management Science, 8, 35–139.
Desrosiers, J., Soumis, F., & Desrochers, M. (1984). Routing with time windows by column generation. Networks, 14(4), 545–565.
Dunbar, M., Belieres, S., Shukla, N., Amirghasemi, M., Perez, P., & Mishra, N. (2018). A genetic column generation algorithm for sustainable spare part delivery: Application to the Sydney Drop Point network. Annals of Operations Research. https://doi.org/10.1007/s10479-018-2911-2
Farley, A. A. (1990). A note on bounding a class of linear programming problems, including cutting stock problems. Operations Research, 38(5), 922–923.
Gelogullari, C. A., & Logendran, R. (2010). Group-scheduling problems in electronics manufacturing. Journal of Scheduling, 13(2), 177–202.
Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849–859.
Gilmore, P. C., & Gomory, R. E. (1963). A linear programming approach to the cutting stock problem-Part II. Operations Research, 11(6), 863–888.
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.
Guinet, A. (1993). Scheduling sequence-dependent jobs on identical parallel machines to minimize completion time criteria. The International Journal of Production Research, 31(7), 1579–1594.
He, C., Lina, H., & Linb, Y. (2015). Bounded serial-batching scheduling for minimizing maximum lateness and makespan. Discrete Optimization, 16, 70–75.
Houck, J. D. J., Picard, J. C., Queyranne, M., & Vemuganti, R. R. (1980). The travelling salesman problem as a constrained shortest path problem: Theory and computational experience. Operations Research, 17, 93–109.
IBM (2009) ILOG CPLEX Optimization Studio (Version 12.2). IBM.
Jahren, E., & Achá, R. A. (2018). A column generation approach and new bounds for the car sequencing problem. Annals of Operations Research, 264, 193–211.
Kramer, A., M. Dell'Amico and M. Iori. (2018). Enhanced arc-flow formulations to minimize weighted completion time on identicsl parallel machines, Technical report, DISMI, UNIMORE.
Kong, M., Liu, X., Pei, J., Cheng, H., & Pardalos, P. M. (2018). A BRKGA-DE algorithm for parallel-batching scheduling with deterioration and learning effects on parallel machines under preventive maintenance consideration. Annals of Mathematics and Artificial Intelligence, 88, 237–267.
Kong, M., Liu, X., Pei, J., Cheng, H., Pardalos, P. M., & Mladenovic, N. (2020). Parallel-batching scheduling with nonlinear processing times on a single and unrelated parallel machines. Journal of Global Optimization, 78, 693–715.
Liao, B., Song, Q., & J. Pei, S. Yang and P.M. Pardalos. (2020). Parallel-machine group scheduling with inclusive processing set restrictions, outsourcing option and serial-batching under the effect of step-deterioration. Journal of Global Optimization, 78, 717–742.
Liu, S., Pei, J., Cheng, H., Liu, X., & Pardalos, P. M. (2019). Two-stage hybrid flow shop scheduling on parallel batching machines considering a job-dependent deteriorating effect and non-identical job sizes. Applied Soft Computing, 84, 105701.
Long, J., Zheng, Z., Gao, X., Pardalos, P. M., & Hu, W. (2020). An effective heuristic based on column generation for the two-dimensional three-stage steel plate cutting problem. Annals of Operations Research, 289, 291–311.
Lopes, M. J. P., & de Carvalho, J. V. (2007). A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times. European Journal of Operational Research, 176(3), 1508–1527.
Lu, S., Liua, X., Pei, J., Thai, M. T., & Pardalos, P. M. (2018). A hybrid ABC-TS algorithm for the unrelated parallel-batching machines scheduling problem with deteriorating jobs and maintenance activity. Applied Soft Computing, 66, 1268–2182.
Lübbecke, M. E., & Desrosiers, J. (2005). Selected topics in column generation. Operations Research, 53(6), 1007–1023.
Matin, N. Z. H., Salmasi, N., & Shahvari, O. (2017). Makespan minimization in flowshop batch processing problem with different batch compositions on machines. International Journal of Production Economics, 193, 832–844.
Ozturk, O. (2020). A truncated column generation algorithm for the parallel batch scheduling problem to minimize total flow time. European Journal of Operational Research, 286(2), 432–443.
Ozturka, O., Begenb, M. A., & Zaric, G. S. (2017). A branch and bound algorithm for scheduling unit size jobs on parallel batching machines to minimize makespan. International Journal of Production Research, 55, 1815–1831.
Pei, J., Cheng, B., Liu, X., Pardalos, P. M., & Kong, M. (2019a). Single-machine and parallel-machine serial-batching scheduling problems with position-based learning effect and linear setup time. Annals of Operations Research, 272, 217–241.
Pei, J., Song, Q., Liao, B., Liu, X., & Pardalos, P. M. (2020a). Parallel-machine serial-batching scheduling with release times under the effects of position-dependent learning and time-dependent deterioration. Annals of Operations Research. https://doi.org/10.1007/s10479-020-03555-2
Pei, J., Liu, X., Fan, W., Pardalos, P. M., & Lu, S. (2019b). A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs, financial budget, and resource constraint in multiple manufacturers. Omega, 82, 55–69.
Pei, J., Liu, X., Pardalos, P. M., Fan, W., & Yang, S. (2017). Scheduling deteriorating jobs on a single serial-batching machine with multiple job types and sequence-dependent setup times. Annals of Operations Research, 249, 175–195.
Pei, Z., Zhang, X., Zheng, L., & Wan, M. (2020b). A column generation-based approach for proportionate flexible two-stage no-wait job shop scheduling. International Journal of Production Research, 58(2), 487–508.
Rauchecker, G., & Schryen, G. (2019). An exact branch-and-price algorithm for scheduling rescue unites during disaster response. European Journal of Operational Research, 272, 352–363.
Rozenknop, A., Wolfler Calvo, R., Alfandari, L., Chemla, D., & Létocart, L. (2013). Solving the electricity production planning problem by a column generation based heuristic. Journal of Scheduling, 16, 585–604.
Schaller, J. E., Gupta, J. N., & Vakharia, A. J. (2000). Scheduling a flowline manufacturing cell with sequence dependent family setup times. European Journal of Operational Research, 125(2), 324–339.
Shahvari, O., & Logendran, R. (2016). Hybrid flow shop batching and scheduling with a bi-criteria objective. International Journal of Production Economics, 179, 239–258.
Shahvari, O., & Logendran, R. (2017a). A bi-objective batch processing problem with dual-resources on unrelated-parallel machines. Applied Soft Computing, 61, 174–192.
Shahvari, O., & Logendran, R. (2017b). An Enhanced tabu search algorithm to minimize a bi-criteria objective in batching and scheduling problems on unrelated-parallel machines with desired lower bounds on batch sizes. Computers & Operations Research, 77, 154–176.
Shahvari, O., & Logendran, R. (2018). A comparison of two stage-based hybrid algorithms for a batch scheduling problem in hybrid flow shop with learning effect. International Journal of Production Economics, 195, 227–248.
Shen, L., Gupta, J. N., & Buscher, U. (2014). Flow shop batching and scheduling with sequence-dependent setup times. Journal of Scheduling, 17(4), 353–370.
Van den Akker, J. M., Hoogeveen, J. A., & van Kempen, J. W. (2012). Using column generation to solve parallel machine scheduling problems with minmax objective functions. Journal of Scheduling, 15, 801–810.
Van Den Akker, J. M., Hurkens, C. A., & Savelsbergh, M. W. (2000). Time-indexed formulations for machine scheduling problems: Column generation. INFORMS Journal on Computing, 12(2), 111–124.
Van Den Akker, J. M., Hoogeveen, J. A., & van de Velde, S. L. (1999). Parallel machine scheduling by column generation. Operations Research, 47(6), 862–872.
Vanderbeck, F., & Wolsey, L. A. (1996). An exact algorithm for IP column generation. Operations Research Letters, 19(4), 151–159.
Wilhelm, W. E. (2001). A technical review of column generation in integer programming. Optimization and Engineering, 2(2), 159–200.