Volume 54, Number 2, March-April 2020
|Page(s)||529 - 553|
|Published online||02 March 2020|
Algorithms for four-machine flowshop scheduling problem with uncertain processing times to minimize makespan
Department of Mathematical Sciences, School of Natural Sciences, Kean University, 1000 Morris Ave, Union, NJ 07083, USA
2 Department of Industrial and Management Systems Engineering, Kuwait University, P.O. Box 5969, Safat, Kuwait
* Corresponding author: email@example.com
Accepted: 27 January 2020
We consider the four-machine flowshop scheduling problem to minimize makespan where processing times are uncertain. The processing times are within some intervals, where the only available information is the lower and upper bounds of job processing times. Some dominance relations are developed, and twelve algorithms are proposed. The proposed algorithms first convert the four-machine problem into two stages, then, use the well-known Johnson’s algorithm, known to yield the optimal solution for the two-stage problem. The algorithms also use the developed dominance relations. The proposed algorithms are extensively evaluated through randomly generated data for different numbers of jobs and different gaps between the lower and upper bounds of processing times. Computational experiments indicate that the proposed algorithms perform well. Moreover, the computational experiments reveal that one of the proposed algorithms, Algorithm A7, performs significantly better than the other eleven algorithms for all possible combinations of the number of jobs and the gaps between the lower and upper bounds. More specifically, error percentages of the other eleven algorithms range from 2.3 to 27.7 times that of Algorithm A7. The results have been confirmed by constructing 99% confidence intervals and tests of hypotheses using a significance level of 0.01.
Mathematics Subject Classification: 20-XX
Key words: Flowshop scheduling / makespan / uncertain processing times / algorithm
© EDP Sciences, ROADEF, SMAI 2020
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.