# 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] Ming-Jong Yao, Tien-Cheng Hsu. An efficient search algorithm for obtaining the optimal replenishment strategies in multi-stage just-in-time supply chain systems. Journal of Industrial & Management Optimization, 2009, 5 (1) : 11-32. doi: 10.3934/jimo.2009.5.11 [2] Li Deng, Wenjie Bi, Haiying Liu, Kok Lay Teo. A multi-stage method for joint pricing and inventory model with promotion constrains. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020097 [3] Ripeng Huang, Shaojian Qu, Xiaoguang Yang, Zhimin Liu. Multi-stage distributionally robust optimization with risk aversion. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019109 [4] Jinghuan Li, Yu Li, Shuhua Zhang. Optimal expansion timing decisions in multi-stage PPP projects involving dedicated asset and government subsidies. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-22. doi: 10.3934/jimo.2019043 [5] Ruijun Zhao, Jemal Mohammed-Awel. A mathematical model studying mosquito-stage transmission-blocking vaccines. Mathematical Biosciences & Engineering, 2014, 11 (5) : 1229-1245. doi: 10.3934/mbe.2014.11.1229 [6] 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 [7] Adel Dabah, Ahcene Bendjoudi, Abdelhakim AitZai. An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029 [8] Jiping Tao, Ronghuan Huang, Tundong Liu. A $2.28$-competitive algorithm for online scheduling on identical machines. Journal of Industrial & Management Optimization, 2015, 11 (1) : 185-198. doi: 10.3934/jimo.2015.11.185 [9] Chunmei Zhang, Wenxue Li, Ke Wang. Graph-theoretic approach to stability of multi-group models with dispersal. Discrete & Continuous Dynamical Systems - B, 2015, 20 (1) : 259-280. doi: 10.3934/dcdsb.2015.20.259 [10] Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391 [11] Huan Su, Pengfei Wang, Xiaohua Ding. Stability analysis for discrete-time coupled systems with multi-diffusion by graph-theoretic approach and its application. Discrete & Continuous Dynamical Systems - B, 2016, 21 (1) : 253-269. doi: 10.3934/dcdsb.2016.21.253 [12] Lalida Deeratanasrikul, Shinji Mizuno. Multiple-stage multiple-machine capacitated lot-sizing and scheduling with sequence-dependent setup: A case study in the wheel industry. Journal of Industrial & Management Optimization, 2017, 13 (1) : 413-428. doi: 10.3934/jimo.2016024 [13] Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269 [14] Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703 [15] Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243 [16] Ling Lin, Dong He, Zhiyi Tan. Bounds on delay start LPT algorithm for scheduling on two identical machines in the $l_p$ norm. Journal of Industrial & Management Optimization, 2008, 4 (4) : 817-826. doi: 10.3934/jimo.2008.4.817 [17] Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057 [18] Xiaoxiao Yuan, Jing Liu, Xingxing Hao. A moving block sequence-based evolutionary algorithm for resource investment project scheduling problems. Big Data & Information Analytics, 2017, 2 (1) : 39-58. doi: 10.3934/bdia.2017007 [19] Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-34. doi: 10.3934/jimo.2019030 [20] Xuewen Huang, Xiaotong Zhang, Sardar M. N. Islam, Carlos A. Vega-Mejía. An enhanced Genetic Algorithm with an innovative encoding strategy for flexible job-shop scheduling with operation and processing flexibility. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-27. doi: 10.3934/jimo.2019088

2018 Impact Factor: 1.025