A lower bounding method for earliness and tardiness minimization on a single batch processing machine

Document Type : Research Paper

Author

School of Industrial Engineering, College of Engineering, Semnan University, Semnan, Iran

Abstract

In this research, the problem of scheduling a single batch processing machine with non-identical job sizes is considered. The objective is to minimize the total earliness and tardiness of all the jobs. A batch processing machine can process a group of jobs simultaneously as a batch as long as its capacity is not violated. The processing time of a batch is equal to the maximum processing time of all the jobs in the batch. Since the problem under study is shown to be NP-hard, a lower bounding method based on column generation is proposed. The proposed lower bound can be used for evaluating the performance of the heuristic and metaheuristic algorithms developed for the research problem. The computational experiments are designed to analyze the performance of the proposed lower bound. The results show that the column generation approach can considerably generates better lower bound than the best known lower bounding method in the literature.

Keywords

Main Subjects


Al-Salamah, M. (2015). Constrained binary artificial bee colony to minimize the makespan for single machine batch processing with non-identical job sizes. Applied Soft Computing, 29, 379-385.
Azizoglu, M. & Webster, S. (2000). Scheduling a batch processing machine with non-identical job sizes. International Journal of Production Research, 38(10), 2173-2184.
Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P. & Vance, P.H. (1998). Branch-and-price: Column generation for solving huge integer programs. Operations Research, 46(3), 316-329.
Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M.Y., Potts, C., Tautenhahn, T. & Van De Velde, S. (1998). Scheduling a batch machine. Journal of Scheduling, 1, 31–54.
Cabo, M., Possani, E., Potts, C.N. & Song, X. (2015). Split–merge: Using exponential neighborhood search for scheduling a batching machine. Computers & Operations Research, 63, 125-135.
Chen, H., Du, B. & Huang, G.Q. (2011). Scheduling a batch processing machine with non-identical job sizes: a clustering perspective. International Journal of Production Research, 49(19), 5755-5778.
Damodaran, P., Ghrayeb, O. & Guttikonda, M.C. (2013). GRASP to minimize makespan for a capacitated batch-processing machine. The International Journal of Advanced Manufacturing Technology, 68(1-4), 407-414.
Damodaran, P., Kumar Manjeshwar, P. & Srihari, K. (2006). Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms. International Journal of Production Economics, 103(2), 882-891.
Dupont, L. & Dhaenens-Flipo, C. (2002). Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure. Computers & Operations Research, 29(7), 807-819.
Dupont, L. & Jolai, F. (1998). Minimizing makespan on a single batch processing machine with non-identical job sizes. European Journal of Automation Systems, 32, 431-440.
Graham, R.L., Lawler, E.L., Lenstra, J.K. & Kan, A. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of discrete Mathematics, 5, 287-326.
Jia, Z.-h., Gao, L.-y. & Zhang, X.-y. (2020). A new history-guided multi-objective evolutionary algorithm based on decomposition for batching scheduling. Expert Systems with Applications, 141, 112920.
Jia, Z.-h. & Leung, J.Y.T. (2014). An improved meta-heuristic for makespan minimization of a single batch machine with non-identical job sizes. Computers & Operations Research, 46(0), 49-58.
Jolai, F. & Dupont, L. (1998). Minimizing mean flow times criteria on a single batch processing machine with non-identical jobs sizes. International Journal of Production Economics, 55(3), 273-280.
Kashan, A.H., Karimi, B. & Jolai, F. (2006). Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizes. International Journal of Production Research, 44(12), 2337-2360.
Kashan, A.H., Karimi, B. & Jolai, F. (2010). An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling on a single batch processing machine with non-identical job sizes. Engineering Applications of Artificial Intelligence, 23(6), 911-922.
Lee, Y.H. & Lee, Y.H. (2013). Minimising makespan heuristics for scheduling a single batch machine processing machine with non-identical job sizes. International Journal of Production Research, 51(12), 3488-3500.
Li, S., Li, G., Wang, X. & Liu, Q. (2005). Minimizing makespan on a single batching machine with release times and non-identical job sizes. Operations Research Letters, 33(2), 157-164.
Li, Z., Chen, H., Xu, R. & Li, X. (2015). Earliness–tardiness minimization on scheduling a batch processing machine with non-identical job sizes. Computers & Industrial Engineering, 87, 590-599.
Malapert, A., Gueret, C. & Rousseau, L.-M. (2012). A constraint programming approach for a batch processing problem with non-identical job sizes. European Journal of Operational Research, 221(3), 533-545.
Melouk, S., Damodaran, P. & Chang, P.-Y. (2004). Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing. International Journal of Production Economics, 87(2), 141-147.
Mönch, L., Fowler, J.W., Dauzère-Pérès, S., Mason, S.J. & Rose, O. (2011). A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations. Journal of Scheduling, 14(6), 583-599.
Mönch, L. & Unbehaun, R. (2007). Decomposition heuristics for minimizing earliness–tardiness on parallel burn-in ovens with a common due date. Computers & Operations Research, 34(11), 3380-3396.
Mönch, L., Unbehaun, R. & Choung, Y.I. (2006). Minimizing earliness–tardiness on a single burn-in oven with a common due date and maximum allowable tardiness constraint. OR Spectrum, 28(2), 177-198.
Ogun, B. & Alabas-Uslu, Ç. (2018). Mathematical models for a batch scheduling problem to minimize earliness and tardiness. Journal of Industrial Engineering and Management (JIEM), 11(3), 390-405.
Polyakovskiy, S., Makarowsky, A. & M'Hallah, R. (2017). Just-in-time batch scheduling problem with two-dimensional bin packing constraints. In:  Proceedings of the Genetic and Evolutionary Computation Conference (pp. 321-328).
Qi, X. & Tu, F. (1999). Earliness and tardiness scheduling problems on a batch processor. Discrete Applied Mathematics, 98(1), 131-145.
Rafiee Parsa, N., Karimi, B. & Husseini, S.M.M. (2017). Exact and heuristic algorithms for the just-in-time scheduling problem in a batch processing system. Computers & Operations Research, 80, 173-183.
Rafiee Parsa, N., Karimi, B. & Husseinzadeh Kashan, A. (2010). A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes. Computers & Operations Research, 37(10), 1720-1730.
Rafiee Parsa, N., Karimi, B. & Moattar Husseini, S.M. (2016). Minimizing total flow time on a batch processing machine using a hybrid max–min ant system. Computers & Industrial Engineering, 99, 372-381.
Rafiee Parsa, N., Keshavarz, T., Karimi, B. & Moattar Husseini, S.M. (2019). A hybrid neural network approach to minimize total completion time on a single batch processing machine. International Transactions in Operational Research, n/a(n/a).
Uzsoy, R. (1994). Scheduling a single batch processing machine with non-identical job sizes. International Journal of Production Research, 32(7), 1615-1635.
Wang, H.-M. (2011). Solving single batch-processing machine problems using an iterated heuristic. International Journal of Production Research, 49(14), 4245-4261.
Wilhelm, W.E. (2001). A technical review of column generation in integer programming. Optimization and Engineering, 2(2), 159-200.
Wilhelm, W.E., Damodaran, P. & Li, J. (2003). Prescribing the content and timing of product upgrades. IIE Transactions, 35(7), 647-663.
Xu, R., Chen, H. & Li, X. (2012). Makespan minimization on single batch-processing machine via ant colony optimization. Computers & Operations Research, 39(3), 582-593.
Zhao, H., Hu, F. & Li, G. (2006). Batch scheduling with a common due window on a single machine. In:  Fuzzy Systems and Knowledge Discovery (pp. 641-645): Springer.
Zhou, S., Chen, H., Xu, R. & Li, X. (2014). Minimising makespan on a single batch processing machine with dynamic job arrivals and non-identical job sizes. International Journal of Production Research, 52(8), 2258-2274.