Meta-heuristic algorithms for scheduling on parallel batch machines with unequal job ready times
Pages 542 - 547
Abstract
This paper address the problem of scheduling a set of jobs with non-zero ready times and incompatible job families on a set of identical parallel batch machines so as to minimize the total weighted tardiness. In this problem, each machine can process several jobs of a same family simultaneously as a batch as long as the machine capacity is not exceeded. Jobs of a family has the same processing time and the batch ready time is equal to the largest ready time among all the jobs in the batch. To solve the problem, we propose two meta-heuristic algorithms based on Iterated Greedy (IG) and Simulated Annealing (SA), respectively. The performance of our algorithms is evaluated and compared by computational experiments on a large benchmark of instances from the literature. The obtained results indicate that the proposed algorithms has good performance compared to two meta-heuristic algorithms proposed for the same problem.
References
[1]
Christian Almeder and Lars Mönch. Metaheuristics for scheduling jobs with incompatible families on parallel batching machines. Journal of the Operational Research Society, 62 (12): 2083–2096, 2011.
[2]
José Elias C Arroyo and Joseph Y-T Leung. An effective iterated greedy algorithm for scheduling unrelated parallel batch machines with nonidentical capacities and unequal ready times. Computers & Industrial Engineering, 2017.
[3]
Hari Balasubramanian, Lars Monch, John Fowler, and Michele Pfund. Genetic algorithm based scheduling of parallel batch machines with incompatible job families to minimize total weighted tardiness. International Journal of Production Research, 42 (8): 1621–1638, 2004.
[4]
Andrew Bilyk, Lars Mönch, and Christian Almeder. Scheduling jobs with ready times and precedence constraints on parallel batch machines using metaheuristics. Computers & Industrial Engineering, 78: 175–185, 2014.
[5]
Tsung-Che Chiang, Hsueh-Chicn Cheng, and Li-Chen Fu. A memetic algorithm for minimizing total weighted tardiness on parallel batch machines with incompatible job families and dynamic job arrival. Computers & Operations Research, 37 (12): 2257–2269, 2010.
[6]
Purushothaman Damodaran and Mario C Velez-Gallego. A simulated annealing algorithm to minimize makespan of parallel batch processing machines with unequal job ready times. Expert Systems with Applications, 39 (1): 1451–1458, 2012.
[7]
Qinma Kang, Hong He, and Huimin Song. Task assignment in heterogeneous computing systems using an effective iterated greedy algorithm. Journal of Systems and Software, 84 (6): 985–992, 2011.
[8]
Dong-Won Kim, Kyong-Hee Kim, Wooseung Jang, and F. Frank Chen. Unrelated parallel machine scheduling with setup times using simulated annealing. Robotics and Computer-Integrated Manufacturing, 18 (3): 223–231, 2002.
[9]
Scott Kirkpatrick, C. Daniel Gelatt, Mario P. Vecchi, et al. Optimization by simmulated annealing. science, 220 (4598): 671–680, 1983.
[10]
Andreas Klemmt, Gerald Weigert, Christian Almeder, and Lars Mönch. A comparison of mip-based decomposition techniques and vns approaches for batch scheduling problems. In Simulation Conference (WSC), Proceedings of the 2009 Winter, pages 1686–1694. IEEE, 2009.
[11]
Stefan Lausch and Lars Mönch. Metaheuristic approaches for scheduling jobs on parallel batch processing machines. In Heuristics, Metaheuristics and Approximate Methods in Planning and Scheduling, pages 187–207. Springer, 2016.
[12]
Kai Li, Shan-Lin Yang, and Hua-Wei Ma. A simulated annealing approach to minimize the maximum lateness on uniform parallel machines. Mathematical and Computer Modelling, 53 (5): 854–860, 2011.
[13]
Lars Monch, Hari Balasubramanian, John W Fowler, and Michele E Pfund. Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times. Computers & Operations Research, 32 (11): 2731–2750, 2005.
[14]
Quan-Ke Pan and Rubén Ruiz. An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem. Omega, 44: 41–50, 2014.
[15]
Michael L. Pinedo. Scheduling: theory, algorithms, and systems. Springer Science & Business Media, 2012.
[16]
Francisco J Rodriguez, Manuel Lozano, Christian Blum, and Carlos Garcií-MartiNez. An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem. Computers & Operations Research, 40 (7): 1829–1841, 2013.
[17]
Rubén Ruiz and Thomas Stützle. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177 (3): 2033–2049, 2007.
[18]
Rubén Ruiz and Thomas Stützle. An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives. European Journal of Operational Research, 187 (3): 1143–1159, 2008.
[19]
Kuo-Ching Ying, Shih-Wei Lin, and Chien-Yi Huang. Sequencing single-machine tardiness problems with sequence dependent setup times using an iterated greedy heuristic. Expert Systems with Applications, 36 (3): 7087–7092, 2009.
Recommendations
Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times
This research analyzes the problem of scheduling a set of n jobs with arbitrary job sizes and non-zero ready times on a set of m unrelated parallel batch processing machines so as to minimize the makespan. Unrelated parallel machine is a generalization ...
An effective iterated greedy algorithm for scheduling unrelated parallel batch machines with non-identical capacities and unequal ready times
We consider the problem of scheduling jobs on unrelated batch machines so as to minimize the makespan.We present a MIP formulation of the problem and present a lower bound on the optimal makespan.We propose an iterated greedy algorithm to solve the ...
Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times
This research is motivated by a scheduling problem found in the diffusion and oxidation areas of semiconductor wafer fabrication, where the machines can be modeled as parallel batch processors. We attempt to minimize total weighted tardiness on parallel ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Oct 2017
3827 pages
Copyright © 2017.
Publisher
IEEE Press
Publication History
Published: 05 October 2017
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 30 Dec 2024