A memetic algorithm for minimizing total weighted tardiness on parallel batch machines with incompatible job families and dynamic job arrival. (English) Zbl 1231.90183
Summary: This paper addresses a scheduling problem motivated by scheduling of diffusion operations in the wafer fabrication facility. In the target problem, jobs arrive at the batch machines at different time instants, and only jobs belonging to the same family can be processed together. Parallel batch machine scheduling typically consists of three types of decisions-batch forming, machine assignment, and batch sequencing. We propose a memetic algorithm with a new genome encoding scheme to search for the optimal or near-optimal batch formation and batch sequence simultaneously. Machine assignment is resolved in the proposed decoding scheme. Crossover and mutation operators suitable for the proposed encoding scheme are also devised. Through the experiment with 4860 problem instances of various characteristics including the number of machines, the number of jobs, and so on, the proposed algorithm demonstrates its advantages over a recently proposed benchmark algorithm in terms of both solution quality and computational efficiency.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Software:
GALibReferences:
| [1] | Gupta, J. N.D.; Ruiz, R.; Fowler, J. W.; Mason, S. J., Operational planning and control of semiconductor wafer production, Production Planning & Control, 17, 7, 639-647 (2006) |
| [2] | Sourirajan, K.; Uzsoy, R., Hybrid decomposition heuristics for solving large-scale scheduling problems in semiconductor wafer fabrication, Journal of Scheduling, 10, 41-65 (2007) · Zbl 1154.90491 |
| [3] | Pfund, M. E.; Balasubramanian, H.; Fowler, J. W.; Mason, S. J.; Rose, O., A multi-criteria approach for scheduling semiconductor wafer fabrication facilities, Journal of Scheduling, 11, 29-47 (2008) · Zbl 1168.90465 |
| [4] | Potts, C. N.; Kovalyov, M. Y., Scheduling with batching: a review, European Journal of Operational Research, 120, 228-249 (2000) · Zbl 0953.90028 |
| [5] | Mathirajan, M.; Sivakumar, A. I., A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor, International Journal of Advanced Manufacturing Technology, 29, 990-1001 (2006) |
| [6] | Uzsoy, R., Scheduling batch processing machines with incompatible job families, International Journal of Production Research, 33, 10, 2685-2708 (1995) · Zbl 0910.90180 |
| [7] | Mehta, S. V.; Uzsoy, R., Minimizing total tardiness on a batch processing machine with incompatible job families, IIE Transactions, 30, 165-178 (1998) |
| [8] | Vepsalainen, A. P.J.; Morton, T. E., Priority rules for job shops with weighted tardiness costs, Management Science, 33, 8, 1035-1047 (1987) |
| [9] | Azizoglu, M.; Webster, S., Scheduling a batch processing machine with incompatible job families, Computers & Industrial Engineering, 39, 325-335 (2001) |
| [10] | Perez, I. C.; Fowler, J. W.; Carlyle, W. M., Minimizing total weighted tardiness on a single batch process machine with incompatible job families, Computers & Operations Research, 32, 327-341 (2005) · Zbl 1073.90015 |
| [11] | Geiger, C. D.; Uzsoy, R., Learning effective dispatching rules for batch processor scheduling, International Journal of Production Research, 46, 6, 1431-1454 (2008) · Zbl 1160.90392 |
| [12] | Koh, S. G.; Koo, P. H.; Kim, D. C.; Hur, W. S., Scheduling a single batch processing machine with arbitrary job sizes and incompatible job families, International Journal of Production Economics, 98, 81-96 (2005) |
| [13] | Kashan, A. H.; Karimi, B., Scheduling a single batch-processing machine with arbitrary job sizes and incompatible job families: an ant colony framework, Journal of the Operational Research Society, 59, 1268-1280 (2008) · Zbl 1176.90222 |
| [14] | Balasubramanian, H.; Mönch, L.; Fowler, J. W.; Pfund, M. E., Genetic algorithm based scheduling of parallel batch machines with incompatible families to minimize total weighted tardiness, International Journal of Production Research, 42, 8, 1621-1638 (2004) · Zbl 1099.90537 |
| [15] | Raghavan NRS, Venkataramana M. Scheduling parallel batch processors with incompatible job families using ant colony optimization. In: Proceedings of the IEEE international conference on automation science and engineering, 2006, p. 507−12.; Raghavan NRS, Venkataramana M. Scheduling parallel batch processors with incompatible job families using ant colony optimization. In: Proceedings of the IEEE international conference on automation science and engineering, 2006, p. 507−12. |
| [16] | Koh, S. G.; Koo, P. H.; Ha, J. W.; Lee, W. S., Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families, International Journal of Production Research, 42, 19, 4091-4107 (2004) · Zbl 1060.90643 |
| [17] | Mathirajan, M.; Sivakumar, A. I., Minimizing total weighted tardiness on heterogeneous batch processing machines with incompatible job families, International Journal of Advanced Manufacturing Technology, 28, 1038-1047 (2006) |
| [18] | Glassey, C. R.; Weng, W. W., Dynamic batching heuristics for simultaneous processing, IEEE Transactions on Semiconductor Manufacturing, 4, 2, 77-82 (1991) |
| [19] | Fowler, J. W.; Phillips, D. T.; Hogg, G. L., Real-time control of multiproduct bulk-service semiconductor manufacturing processes, IEEE Transactions on Semiconductor Manufacturing, 5, 2, 158-163 (1992) |
| [20] | Tangudu, S. K.; Kurz, M. E., A branch and bound algorithm to minimise total weighted tardiness on a single batch processing machine with ready times and incompatible job families, Production Planning & Control, 17, 7, 728-741 (2006) |
| [21] | Gupta, A. K.; Sivakumar, A. I., Controlling delivery performance in semiconductor manufacturing using look ahead batching, International Journal of Production Research, 45, 3, 591-613 (2007) · Zbl 1128.90378 |
| [22] | Kurz, M. E.; Mason, S. J., Minimizing total weighted tardiness on a batch-processing machine with incompatible job families and job ready times, International Journal of Production Research, 46, 1, 131-151 (2008) · Zbl 1128.90404 |
| [23] | Malve, S.; Uzsoy, R., A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families, Computers & Operations Research, 34, 3016-3028 (2007) · Zbl 1185.90086 |
| [24] | Mönch, L.; Balasubramanian, H.; Fowler, J. W.; Pfund, M. E., Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times, Computers & Operations Research, 32, 2731-2750 (2005) · Zbl 1071.90019 |
| [25] | Reichelt, D.; Mönch, L., Multiobjective scheduling of jobs with incompatible families on parallel batch machines, Lecture Notes in Computer Science, 3906, 202-221 (2006) · Zbl 1401.90082 |
| [26] | Wang, C. S.; Uzsoy, R., A genetic algorithm to minimize maximum lateness on a batch processing machine, Computers & Operations Research, 29, 1621-1640 (2002) |
| [27] | Van Der Zee, D. J., Dynamic scheduling of batch-processing machines with non-identical product size, International Journal of Production Research, 45, 10, 2327-2349 (2007) · Zbl 1128.90506 |
| [28] | Kashan, A. H.; Karimi, B.; Jenabi, M., A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes, Computers & Operations Research, 35, 1084-1098 (2008) · Zbl 1180.90126 |
| [29] | Aytug, H.; Khouja, M.; Vergara, F. E., Use of genetic algorithms to solve production and operations management problems: a review, International Journal of Production Research, 41, 17, 3955-4009 (2003) |
| [30] | Chaudhry, S. S.; Luo, W., Application of genetic algorithms in production and operations management: a review, International Journal of Production Research, 43, 19, 4083-4101 (2005) · Zbl 1080.90514 |
| [31] | Hart, E.; Ross, P.; Corne, D., Evolutionary scheduling: a review, Genetic Programming and Evolvable Machines, 6, 191-220 (2005) |
| [32] | França, P. M.; Mendes, A.; Moscato, P., A memetic algorithm for the total tardiness single machine scheduling problem, European Journal of Operational Research, 132, 224-242 (2001) · Zbl 0996.90042 |
| [33] | Tseng, L. Y.; Lin, Y. T., A hybrid genetic local search algorithm on the permutation flowshop scheduling problem, European Journal of Operational Research, 198, 84-92 (2009) · Zbl 1163.90532 |
| [34] | Essafi, I.; Mati, Y.; Dauzère-Pérès, S., A genetic local search algorithm for minimizing total weighted tardines in the job-shop scheduling problem, Computers & Operations Research, 35, 8, 2599-2616 (2008) · Zbl 1177.90155 |
| [35] | Chiang, T. C.; Fu, L. C., A rule-centric memetic algorithm to minimize the number of tardy jobs in the job shop, International Journal of Production Research, 46, 24, 6913-6931 (2008) |
| [36] | Ishibuchi, H.; Yoshida, T.; Murata, T., Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling, IEEE Transactions on Evolutionary Computation, 7, 2, 204-223 (2003) |
| [37] | Cheng HC, Chiang TC, Fu LC. Multiobjective job shop scheduling using memetic algorithm and shifting bottleneck procedures. In: Proceedings of the IEEE symposium on computational intelligence in scheduling, 2009, p. 15-21.; Cheng HC, Chiang TC, Fu LC. Multiobjective job shop scheduling using memetic algorithm and shifting bottleneck procedures. In: Proceedings of the IEEE symposium on computational intelligence in scheduling, 2009, p. 15-21. |
| [38] | Cheng HC, Chiang TC, Fu LC. A memetic algorithm for parallel batch machine scheduling with incompatible job families and dynamic job arrivals. In: Proceedings of the IEEE international conference on systems, man, and cybernetics, 2008, p. 541-46.; Cheng HC, Chiang TC, Fu LC. A memetic algorithm for parallel batch machine scheduling with incompatible job families and dynamic job arrivals. In: Proceedings of the IEEE international conference on systems, man, and cybernetics, 2008, p. 541-46. |
| [39] | Wall, M. GAlib: a C++ library of genetic algorithms components. 〈http://lancet.mit.edu/ga/; Wall, M. GAlib: a C++ library of genetic algorithms components. 〈http://lancet.mit.edu/ga/ |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
