Recent researches show that there are some anomalies, which are not satisfied with common sense, appearing in some special permutation flow shop scheduling problems (PFSPs). These anomalies can be divided into three different types, such as changing the processing time of some operations, changing the number of total jobs and changing the number of total machines. This paper summarizes these three types of anomalies showing in the special PFSPs and gives some examples to make them better understood. The extended critical path is proposed and the reason why these anomalies happen in special PFSPs is given: anomalies will occur in these special PFSPs when the time of the operations on the reverse critical path changes. After that, the further reason for these anomalies is presented that when any one of these three types of anomalies happens, the original constraint in the special PFSPs is destroyed, which makes the anomalies appear. Finally, the application of these anomalies in production practice is given through examples and also with the possible research directions. The main contribution of this research is analyzing the intial reason why the anomalies appear in special PFSPs and pointing out the application and the possible research directions of all these three types of anomalies.
Lin Gui
,
Liang Gao
,
Xinyu Li
. Anomalies in Special Permutation Flow Shop Scheduling Problems[J]. Chinese Journal of Mechanical Engineering, 2020
, 33(3)
: 46
-46
.
DOI: 10.1186/s10033-020-00462-2
Recent researches show that there are some anomalies, which are not satisfied with common sense, appearing in some special permutation flow shop scheduling problems (PFSPs). These anomalies can be divided into three different types, such as changing the processing time of some operations, changing the number of total jobs and changing the number of total machines. This paper summarizes these three types of anomalies showing in the special PFSPs and gives some examples to make them better understood. The extended critical path is proposed and the reason why these anomalies happen in special PFSPs is given: anomalies will occur in these special PFSPs when the time of the operations on the reverse critical path changes. After that, the further reason for these anomalies is presented that when any one of these three types of anomalies happens, the original constraint in the special PFSPs is destroyed, which makes the anomalies appear. Finally, the application of these anomalies in production practice is given through examples and also with the possible research directions. The main contribution of this research is analyzing the intial reason why the anomalies appear in special PFSPs and pointing out the application and the possible research directions of all these three types of anomalies.
[1] Kunkun Peng, Long Wen, Ran Li, et al. An effective hybrid algorithm for permutation flow shop scheduling problem with setup time. Procedia CIRP, 2018: 1288-1292.
[2] J Gmys, M Mezmaz, N Melab, et al. A computationally efficient Branchand-Bound algorithm for the permutation flow-shop scheduling problem. European Journal of Operational Research, 2020, 283(3): 814-833.
[3] Fernandezviagas, Victor, Jose M Molinapariente, Jose M Framinan. Generalised accelerations for insertion-based heuristics in permutation flowshop scheduling. European Journal of Operational Research, 2020, 282(3): 858-872.
[4] Enda Jiang, Ling Wang. An improved multi-objective evolutionary algorithm based on decomposition for energy-efficient permutation flow shop scheduling problem with sequence-dependent setup time. International Journal of Production Research, 2019, 57(6): 1756-1771.
[5] Ning Zhao, Song Ye, Kaidian Li, et al. Effective iterated greedy algorithm for flow-shop scheduling problems with time lags. Chinese Journal of Mechanical Engineering, 2017, 30(3): 652-662.
[6] Allahverdi Ali, Harun Aydilek, Asiye Aydilek. No-wait flow shop scheduling problem with separate setup times to minimize total tardiness subject to makespan. Applied Mathematics and Computation, 2020, 365(15): 124688.
[7] Fuqing Zhao, Huan Liu, Yi Zhang, et al. A discrete water wave optimization algorithm for no-wait flow shop scheduling problem. Expert Systems With Applications, 2018, 91: 347-363.
[8] Xueqi Wu, Ada Che. Energy-efficient no-wait permutation flow shop scheduling by adaptive multi-objective variable neighborhood search. Omega, 2019, 94: 102117.
[9] Weishi Shao, Dechang Pi, Zhongshi Shao. Memetic algorithm with node and edge histogram for no-idle flow shop scheduling problem to minimize the makespan criterion. Applied Soft Computing, 2017, 54: 164-182.
[10] Jingnan Shen, Ling Wang, Shengyao Wang. A bi-population EDA for solving the no-idle permutation flow-shop scheduling problem with the total tardiness criterion. Knowledge Based Systems, 2015, 74(1): 167-175.
[11] Riahi Vahid, Raymond Chiong, Yuli Zhang. A new iterated greedy algorithm for no-idle permutation flowshop scheduling with the total tardiness criterion. Computers & Operations Research, 2020.
[12] Rossit Daniel Alejandro, Fernando Tohmé, Mariano Frutos. The nonpermutation flow-shop scheduling problem: a literature review. Omega, 2018, 77: 143-153.
[13] Sana Abdollahpour, Javad Rezaeian. Minimizing makespan for flow shop scheduling problem with intermediate buffers by using hybrid approach of artificial immune system. Applied Soft Computing, 2015: 44-56.
[14] Newton M. A Hakim, Vahid Riahi, Abdul Sattar. Makespan preserving flowshop reengineering via blocking constraints. Computers & Operations Research, 2019.
[15] Stefan Waldherr, Sigrid Knust. Decomposition algorithms for synchronous flow shop problems with additional resources and setup times. European Journal of Operational Research, 2017, 259(3): 847-863.
[16] Stefan Waldherr, Sigrid Knust. Complexity results for flow shop problems with synchronous movement. European Journal of Operational Research, 2015, 242(1): 34-44.
[17] Matthias Bultmann, Sigrid Knust, Stefan Waldherr. Synchronous flow shop scheduling with pliable jobs. European Journal of Operational Research, 2018, 270(3): 943-956.
[18] Abadi, IN Kamal, Nicholas G. Hall, Chelliah Sriskandarajah. Minimizing cycle time in a blocking flow shop. Operations Research, 2000, 48(1): 177-180.
[19] Spieksma Frits CR, Gerhard J Woeginger. The no-wait flow-shop paradox. Operations Research Letters, 2005, 33(6): 603-608.
[20] Kalczynski Pawel Jan, Jerzy Kamburowski. On no-wait and no-idle flow shops with makespan criterion. European Journal of Operational Research, 2007, 178(3): 677-685.
[21] Quanke Pan, Baohua Zhao, Yugui Qu. Heuristics for the no-wait flow shop problem with makespan criterion. Chinese Journal of Computers, 2008, 31(7): 1147-1154.
[22] S Waldherr, S Knust, D Briskorn. Synchronous flow shop problems: How much can we gain by leaving machines idle? Omega, 2017, 72: 15-24.
[23] S S Panwalkar, Christos Koulamas. The evolution of schematic representations of flow shop scheduling problems. Journal of Scheduling, 2019, 22(4): 379-391.
[24] S S Panwalkar, Christos Koulamas. Analysis of flow shop scheduling anomalies. European Journal of Operational Research, 2020, 280(1): 25-33.
[25] Aya Ishigaki, Yuki Matsui. Effective neighborhood generation method in search algorithm for flexible job shop scheduling problem. International Journal of Automation Technology, 2019, 13(3): 389-396.
[26] Dunbing Tang, Min Dai. Energy-efficient approach to minimizing the energy consumption in an extended job-shop scheduling problem. Chinese Journal of Mechanical Engineering, 2015, 28(5): 1048-1055.
[27] G M Appa. The transportation problem and its variants. Journal of the Operational Research Society, 1973, 24(1): 79-99.
[28] David J Robb. The "More for Less" paradox in distribution models: An intuitive explanation. IIE Transactions, 1990, 22(4): 377-378.
[29] Szwarc Wlodzimierz. The transportation paradox. Naval Research Logistics Quarterly, 1971, 18(1): 185-202.
[30] Roughgarden Tim, éva Tardos. How bad is selfish routing? Journal of the ACM (JACM), 2002, 49(2): 236-259.
[31] Belady Laszlo A, Robert A Nelson, Gerald S Shedler. An anomaly in spacetime characteristics of certain programs running in a paging machine. Communications of the ACM, 1969, 12(6): 349-353.
[32] Graham Ronald L. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 1969, 17(2): 416-429.
