Minimizing total completion time for flowshop scheduling problem with uncertain processing times
RAIRO. Operations Research, Tome 55 (2021), pp. S929-S946

The four-machine flowshop scheduling problem is investigated with the objective of minimizing total completion time. Job processing times are uncertain where only the lower and upper bounds are known. This problem is common in some manufacturing environments. Some mathematical (dominance) relations are established, and an algorithm (with ten scenarios) is proposed. The proposed algorithm converts the four-machine problem to a single machine problem for which an optimal solution is known for the deterministic problem. The difference among the scenarios is related to the weights assigned to the lower and upper bounds of processing times on the machines. The proposed algorithm is further improved by the established mathematical relations and are evaluated based on extensive computational experiments. The computational results indicate that three scenarios of the proposed algorithm perform much better than the others, and the errors of these three scenarios get better as the size of the problem increases. The results are statistically verified by constructing the confidence intervals.

DOI : 10.1051/ro/2020022
Classification : 90-XX
Keywords: Scheduling, total completion time, uncertain processing times 
@article{RO_2021__55_S1_S929_0,
     author = {Allahverdi, Muberra and Allahverdi, Ali},
     title = {Minimizing total completion time for flowshop scheduling problem with uncertain processing times},
     journal = {RAIRO. Operations Research},
     pages = {S929--S946},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ro/2020022},
     mrnumber = {4223148},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2020022/}
}
TY  - JOUR
AU  - Allahverdi, Muberra
AU  - Allahverdi, Ali
TI  - Minimizing total completion time for flowshop scheduling problem with uncertain processing times
JO  - RAIRO. Operations Research
PY  - 2021
SP  - S929
EP  - S946
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2020022/
DO  - 10.1051/ro/2020022
LA  - en
ID  - RO_2021__55_S1_S929_0
ER  - 
%0 Journal Article
%A Allahverdi, Muberra
%A Allahverdi, Ali
%T Minimizing total completion time for flowshop scheduling problem with uncertain processing times
%J RAIRO. Operations Research
%D 2021
%P S929-S946
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2020022/
%R 10.1051/ro/2020022
%G en
%F RO_2021__55_S1_S929_0
Allahverdi, Muberra; Allahverdi, Ali. Minimizing total completion time for flowshop scheduling problem with uncertain processing times. RAIRO. Operations Research, Tome 55 (2021), pp. S929-S946. doi: 10.1051/ro/2020022

A. Allahverdi, The tricriteria two-machine flowshop scheduling problem. Int. Trans. Oper. Res. 8 (2001) 403–425. | MR | Zbl | DOI

A. Allahverdi, A new heuristic for m -machine flowshop scheduling problem with bicriteria of makespan and maximum tardiness. Comput. Oper. Res. 31 (2004) 157–180. | MR | Zbl | DOI

A. Allahverdi, The third comprehensive survey on scheduling problems with setup times/costs. Eur. J. Oper. Res. 246 (2015) 345–378. | MR | DOI

A. Allahverdi, A survey of scheduling problems with no-wait in process. Eur. J. Oper. Res. 255 (2016) 665–686. | MR | DOI

A. Allahverdi and M. Allahverdi, Two-machine no-wait flowshop scheduling problem with uncertain setup times to minimize maximum lateness. Comput. Appl. Math. 37 (2018) 6774–6794. | MR | DOI

A. Allahverdi and H. Aydilek, Heuristics for two-machine flowshop scheduling problem to minimize makespan with bounded processing times. Int. J. Prod. Res. 48 (2010) 6367–6385. | Zbl | DOI

A. Allahverdi and H. Aydilek, Heuristics for two-machine flowshop scheduling problem to minimize maximum lateness with bounded processing times. Comput. Math. Appl. 60 (2010) 1374–1384. | MR | Zbl | DOI

A. Allahverdi and H. M. Soroush, The significance of reducing setup times/setup costs. Eur. J. Oper. Res. 187 (2008) 978–984. | Zbl | DOI

M. Allahverdi and A. Allahverdi, Algorithms for four-machine flowshop scheduling problem with uncertain processing times to minimize makespan. RAIRO: OR 54 (2020) 529–553. | MR | Zbl | Numdam | DOI

M. Allahverdi and A. Allahverdi, Minimizing total completion time in a two-machine no-wait flowshop with uncertain and bounded setup times. J. Ind. Manage. Optim. 16 (2020) 2439–2457. | MR | DOI

M. Allahverdi, H. Aydilek, A. Aydilek and A. Allahverdi, A better dominance relation and heuristics for two-machine no-wait flowshops with maximum lateness performance measure. To appear in: J. Ind. Manage. Optim. (2020). doi: | DOI | MR

A. Allahverdi and Y. N. Sotskov, Two-machine flowshop minimum length scheduling problem with random and bounded processing times. Int. Trans. Oper. Res. 10 (2003) 65–76. | MR | Zbl | DOI

A. Aydilek, H. Aydilek and A. Allahverdi, Increasing the profitability and competitiveness in a production environment with random and bounded setup times. Int. J. Prod. Res. 51 (2013) 106–117. | DOI

A. Aydilek, H. Aydilek and A. Allahverdi, Production in a two-machine flowshop scheduling environment with uncertain processing and setup times to minimize makespan. Int. J. Prod. Res. 53 (2015) 2803–2819. | DOI

A. Aydilek, H. Aydilek and A. Allahverdi, Algorithms for minimizing the number of tardy jobs for reducing production cost with uncertain processing times. Appl. Math. Model. 45 (2017) 982–996. | MR | DOI

H. Aydilek and A. Allahverdi, Two-machine flowshop scheduling problem with bounded processing times to minimize total completion time. Comput. Math. Appl. 59 (2010) 684–693. | Zbl | DOI

J. F. Chen, Unrelated parallel-machine scheduling to minimize total weighted completion time. J. Intel. Manuf. 26 (2015) 1099–1112. | DOI

J. M. Framinan and P. Perez-Gonzalez, The 2-stage assembly flowshop scheduling problem with total completion time: efficient constructive heuristic and metaheuristic. Comput. Oper. Res. 88 (2017) 237–246. | MR | DOI

J. M. Framinan and P. Perez-Gonzalez, New approximate algorithms for the customer order scheduling problem with total completion time objective. Comput. Oper. Res. 78 (2017) 181–192. | MR | DOI

H. Y. Fuchigami and S. Rangel, A survey of case studies in production scheduling: Analysis and perspectives. J. Comput. Sci. 25 (2018) 425–436. | DOI

E. M. Gonzalez-Neira, D. Ferone, S. Hatami and A. A. Juan, A biased-randomized simheuristic for the distributed assembly permutation flowshop problem with stochastic processing times. Simul. Model. Pract. Theory 79 (2017) 23–36. | DOI

T. Keshavarz and N. Salmasi, Makespan minimization in flexible flowshop sequence-dependent group scheduling problem. Int. J. Prod. Res. 51 (2013) 6182–6193. | DOI

P. Kouvelis and G. Yu, Robust Discrete Optimization and its Applications. Kluwer Academic Publisher, Dordrecht (1997). | MR | Zbl | DOI

T. C. Lai and Y. N. Sotskov, Sequencing with uncertain numerical data for makespan minimization. J. Oper. Res. Soc. 50 (1999) 230–243. | Zbl | DOI

T. C. Lai, Y. N. Sotskov, N. Y. Sotskova and F. Werner, Optimal makespan scheduling with given bounds of processing times. Math. Comput. Model. 26 (1997) 67–86. | MR | Zbl | DOI

M. Pinedo, Scheduling Theory, Algorithms, and Systems. Prentice Hall, Englewood Cliffs, NJ (1995) 349. | Zbl

H. Seidgar, M. Kiani, M. Abedi and H. Fazlollahtabar, An efficient imperialist competitive algorithm for scheduling in the two-stage assembly flow shop problem. Int. J. Prod. Res. 52 (2014) 1240–1256. | DOI

Y. N. Sotskov, A. Allahverdi and T. C. Lai, Flowshop scheduling problem to minimize total completion time with random and bounded processing times. J. Oper. Res. Soc. 55 (2004) 277–286. | Zbl | DOI

P. Tayanithi, S. Manivannan and J. Banks, A knowledge-based simulation architecture to analyze interruptions in a flexible manufacturing system. J. Manuf. Syst. 11 (1992) 195–214. | DOI

K. Wang and S. H. Choi, A decomposition-based approach to flexible flow shop scheduling under machine breakdown. Int. J. Prod. Res. 50 (2012) 215–234. | DOI

Cité par Sources :