Exact and heuristic approaches for scheduling parallel stress test machines in semiconductor reliability laboratories

Abstract We consider a parallel-machine scheduling problem motivated by stress test activities in semiconductor reliability laboratories. Unequal sizes of the jobs and ready times are possible. Several jobs can be processed at the same time on a machine if the sum of their sizes does not exceed the capacity of the machine. The jobs belong to incompatible families. Only jobs of the same family can be processed at the same time on a machine. In contrast to conventional p-batching machines, the machines can be interrupted to start a new job or to unload a completed job. A conditioning time is required to reach again the necessary temperature for the stress tests. A machine is considered as unavailable during the conditioning. Jobs that cannot be completed before a conditioning period of a machine can continue after the machine is available again, i.e., we assume resumable jobs. The makespan or the total (weighted) completion time are the performance measures of interest. The combination of p-batching with processing interruptions is novel and makes these scheduling problems challenging to tackle. We prove that these scheduling problems are NP-hard. Mixed-integer linear programming and constraint programming formulations are established. Constructive heuristics and metaheuristics are designed. Computational experiments based on randomly generated problem instances demonstrate that the proposed algorithms perform well with respect to solution quality and solution time.