Article ID: | iaor2003261 |
Country: | United Kingdom |
Volume: | 29 |
Issue: | 8 |
Start Page Number: | 995 |
End Page Number: | 1007 |
Publication Date: | Jul 2002 |
Journal: | Computers and Operations Research |
Authors: | Sung C.S., Choung Y.I., Hong J.M., Kim Y.H. |
Keywords: | scheduling, programming: dynamic |
This paper considers a scheduling problem for a single burn-in oven in the semiconductor manufacturing industry where the oven is a batch processing machine and each batch processing time is represented by the largest processing time among those of all the jobs contained in the batch. Each job belongs to one of the given number of families. Moreover, the release times of the jobs are different from one another. The objective measure of the problem is the maximum completion time (makespan) of all jobs. A dynamic programming algorithm is proposed in the order of polynomial time complexity for a situation where the number of job families is given (fixed). A computational experiment is performed to compare the time complexity of the proposed algorithm with that of another exact algorithm evaluating all possible job sequences based on batching–dynamic programming. The results of the experiment show that the proposed algorithm is superior to the other.