A COMPARATIVE STUDY ON THREE GRAPH-BASED CONSTRUCTIVE ALGORITHMS FOR MULTI-STAGE SCHEDULING WITH BLOCKING

摘要

In this paper, the blocking conditions are investigated in permutation flow shop, general flow shop and job shop environments, in which there are no buffer storages between any pair of machines. Based on an alternative graph that is an extension of classical disjunctive graph, a new and generic polynomial-time algorithm is proposed to construct a feasible schedule with a given job processing sequence, especially for satisfying complex blocking constraints in multi-stage scheduling environments. To highlight the state-of-the-art of the proposed algorithm, a comparative analysis is conducted in comparison to two other constructive algorithms in the literature. The comparison shows that the proposed algorithm has the following advantages: i) it is more adaptive because it can be applied to three different types of scheduling problems (i.e., permutation flow-shop, general flow-shop and job-shop) without any modifications; ii) it is able to quickly evaluate whether a schedule is feasible (acyclic) or infeasible (cyclic) through checking the availability of the topological order in a directed alternative graph model; iii) it is able to determine the critical path which is useful to design the neighborhood moves in the development of metaheuristics.