Abstract
This paper considers a single batch machine dynamic scheduling problem, which is readily found in the burn-in operation of semiconductor manufacturing. The batch machine can process several jobs as a batch simultaneously, within the capacity limit of the machine, and the processing time is represented by the longest processing time among all jobs in a batch. For a single batch machine problem with arbitrary job release time, we proposed an improved algorithm (merge-split procedure) to refine the solution obtained by the LPT-BFF heuristic, and two versions of a hybrid genetic algorithm (GA) are introduced in this paper. Each version of the hybrid GA diversifies job sequences using the GA operators in stage 1, forms batches in stage 2, and finally sequence the batches in stage 3. The difference is that merge-split procedures are involved in the second version of the hybrid GA. Computational experiments showed that the hybrid GA would obtain satisfactory average solution quality and the merge-split procedures would be good at reinforcing the solution consistency of the hybrid GA.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Ikura Y, Gimple M (1986) Scheduling algorithms for a single batch processing machine. Oper Res Lett 5:61−65
Lee C-Y, Uzsoy R, Martin-Vega LA (1992) Efficient algorithms for scheduling semiconductor burn-in operations. Oper Res 40:764−775
Li C-L, Lee C-Y (1997) Scheduling with agreeable release times and due dates on a batch processing machine. Eur J Oper Res 96:564−569
Sung CS, Kim YH (2003) Minimizing due date related performance measures on two batch processing machines. Eur J Oper Res 147:644−656
Chandru V, Lee C-Y, Uzsoy R (1993) Minimizing total completion time on batch processing machines. Int J Prod Res 31:2097−2121
Dupont L, Ghazvini FJ (1997) A branch and bound algorithm for minimizing mean flow time on a single batch processing machine. Int J Ind Eng 4:197−203
Hochbaum DS, Landy D (1997) Scheduling semiconductor burn-in operations to minimize total flowtime. Oper Res 45:874−885
Lee C-Y, Uzsoy R (1999) Minimizing makespan on a single batch processing machine with dynamic job arrivals. Int J Prod Res 37:219−236
Dupont L, Dhaenens-Flipo C (2002) Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure. Comput Oper Res 29:807−819
Uzsoy R (1994) Scheduling a single batch processing machine with non-identical job sizes. Int J Prod Res 32:1615−1635
Zhang G, Cai X, Lee C-Y, Wong CK (2001) Minimizing makespan on a single batch processing machine with nonidentical job sizes. Nav Res Log 48:226−240
Sung CS, Choung YI (2000) Minimizing makespan on a single burn-in oven in semiconductor manufacturing. Eur J Oper Res 120:559−574
Sung CS, Choung YI, Hong JM, Kim YH (2002) Minimizing makespan on a single burn-in oven with job families and dynamic job arrivals. Comput Oper Res 29:995−1007
Michalewicz Z (1996) Genetic Algorithms+data structrues = evolution algorithms. Springer, Berlin Heidelberg New York
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chou, FD., Chang, PC. & Wang, HM. A hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem. Int J Adv Manuf Technol 31, 350–359 (2006). https://doi.org/10.1007/s00170-005-0194-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-005-0194-7