Scheduling Jobs on a Single Machine With Dirt Cleaning Consideration to Minimize Total Completion Time

Abstract

This paper studies a single-machine scheduling problem observed in the wafer manufacturing process, where the machine must receive periodical maintenance so that the dirt generated in the process does not exceed the limit. The objective is to minimize the total completion times. A mixed binary integer programming model is formulated, and, due to its computational intractability for large problems, three effective heuristics are proposed based on our developed properties. The proposed heuristics are evaluated by comparison with exact solutions on small problems and with lower bounds on large problems. The experimental results show that the INDEX-LOE heuristic yields high-quality solutions in comparison with those obtained from the other two heuristics. Furthermore, the impacts of dirt accumulation and cleaning time are discussed in detail.

Keywords

• Scheduling
• total completion time
• machine unavailability
• mixed binary integer programming
• heuristic algorithms