A modified shifting bottleneck heuristic and disjunctive graph for job shop scheduling problems with transportation constraints

摘要

In this paper, we consider job shop scheduling problems with transportation constraints and bounded processing times. We use a modified disjunctive graph to represent the whole characteristics and constraints of such considered problems. Compared with classical disjunctive graph, it contains not only processing nodes, but also transportation and storage nodes. There are also positive and negative arcs for bounded processing time constraints, transportation times and minimum and maximum allowed storage times before and after each processing task. The objective is to minimise makespan. A feasible solution for makespan is found, if its associated graph contains no positive cycle. A modified shifting bottleneck procedure is used to solve the studied job shop problems which are represented by disjunctive graphs. It is coupled with a heuristic for assigning and sequencing transportation tasks iteratively. To validate our approach, several types of benchmarks with fixed or bounded processing times are tested, corresponding to flexible manufacturing systems, robotic cells and surface treatment facilities. Computational results show that the modified disjunctive graph and the proposed method are efficient and can deal with various cases.