HEURISTIC ALGORITHMS FOR SCHEDULING IN A MULTIPROCESSOR TWO-STAGE FLOWSHOP WITH 0-1 RESOURCE REQUIREMENTS

摘要

This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines at the first stage and a single machine at the second stage. At the first stage, jobs use some additional resources which are available in limited quantities at any time. The resource requirements are of 0-1 type. The objective is the minimization of makespan. The problem is NP-hard. Heuristic algorithms are proposed which, while solving to optimality the resource constrained scheduling problem at the first stage of the flowshop, select for simultaneous processing jobs according to rules promising a good (short) schedule in the flowshop. Several rules of job selection are considered. The performance of the proposed heuristic algorithms is analyzed by comparing their solutions with the lower bound on the optimal makespan. The results of computational experiments show that these heuristics are able to produce near-optimal solutions in short computation time.