# American Institute of Mathematical Sciences

• Previous Article
A parallel water flow algorithm with local search for solving the quadratic assignment problem
• JIMO Home
• This Issue
• Next Article
Closed-loop supply chain network equilibrium model with retailer-collection under legislation
January  2019, 15(1): 221-233. doi: 10.3934/jimo.2018040

## A comparative study on three graph-based constructive algorithms for multi-stage scheduling with blocking

 1 School of Economics and Management, University of Electronic Science and Technology of China, Chengdu 611731, China 2 School of Economics and Management, Fuzhou University, Fujian Province 350108, China 3 School of Mathematical Sciences, Queensland University of Technology, 2 George St, Brisbane Queensland 4001, Australia

* Corresponding author: Shi Qiang Liu

Received  May 2017 Revised  November 2017 Published  April 2018

Fund Project: This work was partially supported by the National Natural Science Foundation of China under Grant Nos. 71571032, 71531003, 71572156 and 71572030.

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.

Citation: Pengyu Yan, Shi Qiang Liu, Cheng-Hu Yang, Mahmoud Masoud. A comparative study on three graph-based constructive algorithms for multi-stage scheduling with blocking. Journal of Industrial & Management Optimization, 2019, 15 (1) : 221-233. doi: 10.3934/jimo.2018040
##### References:

show all references

##### References:
Blocking conditions on a pair of operations processed on the same machine
The result of a three-machine four-job BPFSS instance, obtained by the proposed alternative-graph-based constructive algorithm
The result of a three-machine four-job BPFSS instance, obtained by the directed-graph-based constructive algorithm
A directed alternative graph for a feasible BJSS schedule
A cyclic directed alternative graph for an infeasible BGFSS schedule
A cyclic directed alternative graph for an infeasible BGFSS schedule
The processing times of four jobs in a numerical example
 M1 M2 M3 J1 p1=1 p5=3 p9=3 J2 p2=1 p6=2 p10=2 J3 p3=4 p7=1 p11=4 J4 p4=2 p8=2 p12=2
 M1 M2 M3 J1 p1=1 p5=3 p9=3 J2 p2=1 p6=2 p10=2 J3 p3=4 p7=1 p11=4 J4 p4=2 p8=2 p12=2
 [1] Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781 [2] Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68. [3] J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008 [4] Dmitry Treschev. A locally integrable multi-dimensional billiard system. Discrete & Continuous Dynamical Systems - A, 2017, 37 (10) : 5271-5284. doi: 10.3934/dcds.2017228 [5] Yunfei Lv, Rong Yuan, Yuan He. Wavefronts of a stage structured model with state--dependent delay. Discrete & Continuous Dynamical Systems - A, 2015, 35 (10) : 4931-4954. doi: 10.3934/dcds.2015.35.4931 [6] Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

2019 Impact Factor: 1.366