Scheduling Jobs on a Single Stress Test Machine in a Reliability Laboratory

We consider a single-machine scheduling problem with unequal job sizes and ready times. Several jobs can be processed at the same time on the machine if the sum of their sizes does not exceed the capacity of the machine. Only jobs of the same family can be processed at the same time. The machine can be interrupted to start a new job or to unload a completed job. A conditioning time is required to reach again the temperature for the stress test. The machine is unavailable during conditioning. Jobs that cannot be completed before conditioning have to continue with processing after the machine is available again. The makespan is to be minimized. A mixed-integer linear program and a constraint programming formulation are established, and a constructive heuristic and a biased random-key genetic algorithm are designed. Computational experiments based on randomly generated problem instances demonstrate that the algorithms perform well.