Preemptive scheduling with changeovers: Using column generation technique and genetic algorithm

This paper considers the problem of the scheduling of preemptive jobs on unrelated parallel machines, which differs from those discussed in the literature in that it includes changeovers of machines as well as temporary constraints of resources. This problem is complicated to such an extent that even its mathematical formulation seems impossible. Its solution calls therefore for the introduction of some heuristics. The paper presents a two-stage heuristic integrating the column generation technique with a genetic algorithm for the purpose of minimizing the makespan and the total cost of changeovers. The quality of this heuristic is evaluated by comparing the solutions to a lower bound on the objective function optimal value. An integer-linear programming procedure determining the lower bound is proposed. Extensive experimental study shows that the two-stage heuristic presented is effective for medium-size problems with strong temporary resource constraints in the case of the total cost of changeovers being not in excess of 10% of the makespan cost.