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 cast of changeovers being not in excess of 10% of the makespan cost. (C) 1999 Elsevier Science Ltd. All rights reserved.
preemptive scheduling genetic algorithm parallel machines resource constraints changeover costs column generation algorithm