An improved memetic algorithm to minimize earliness–tardiness on a single batch processing machine

Document Type: Research Paper

Authors

Department of Industrial Engineering and Management Systems, Amirkabir University of Technology, Tehran, Iran

Abstract

In this research, a single batch processing machine scheduling problem with minimization of total earliness and tardiness as the objective function is investigated.We first formulate the problem as a mixed integer linear programming model. Since the research problem is shown to be NP-hard, an improved memetic algorithmis proposed to efficiently solve the problem. To further enhance the memetic algorithm and avoid premature convergence, we hybridize it with a variable neighborhood search procedureas its local search engine. A dynamic programming approach is also proposed to find optimal schedule for a given set of batches. Wedesign a Taguchi experiment to evaluate the effects of different parameters on the performance of the proposed algorithm. The results of an extensive computational study demonstrate the efficacy of the proposed algorithm.

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.

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.

Cheng, B., Li, K. & Chen, B. (2010). Scheduling a single batch-processing machine with non-identical job sizes in fuzzy environment using an improved ant colony optimization. Journal of Manufacturing Systems, 29(1), 29-34.

Coffman, E.G., Garey, M.R. & Johnson, D.S. (1997). Approximation algorithms for bin packing: a survey. In: S.H. Dorit, Approximation algorithms for NP-hard problems (pp. 46-93): PWS Publishing Co.

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.

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.

Hart, W.E., Krasnogor, N. & Smith, J.E. (2005). Recent advances in memetic algorithms (Vol. 166): Springer Verlag.

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.

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.

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.

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.

Moscato, P. (1989). On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech Concurrent Computation Program, C3P Report, 826.

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

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. & 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.

Taguchi, G. (1986). Introduction to quality engineering: designing quality into products and processes: Asian productivity organization.

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.

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.