<abstract xmlns="http://www.w3.org/1999/xhtml"><p>We address the <italic>m</italic>-machine no-wait flowshop scheduling problem; where the objective is to minimize total tardiness. To the best of our knowledge, the considered problem has not been addressed so far. We propose heuristic solutions since the problem is <italic>NP</italic>-hard. Initially, we consider a number of dispatching rules commonly used for the considered objective in other scheduling environments. We identify through computational experiments the best performing dispatching rule; and then propose simulated annealing (<italic>SA</italic>) and genetic algorithms (<italic>GA</italic>) by using the best performing dispatching rule as an initial solution. This achieves at least 50% improvement in the <italic>SA </italic>and <italic>GA </italic>performances. Next, we propose enhanced versions of <italic>SA </italic>and <italic>GA </italic>and show through computational experiments that the enhanced versions provide over 90% further improvement. The performance of enhanced <italic>GA </italic>is slightly better than that of enhanced <italic>SA</italic>; however, the computation time of enhanced <italic>GA </italic>is about 10 times that of enhanced <italic>SA</italic>. Therefore, we conclude that the enhanced <italic>SA </italic>outperforms the enhanced <italic>GA</italic>.</p></abstract>

We address the m-machine no-wait flowshop scheduling problem; where the objective is to minimize total tardiness. To the best of our knowledge, the considered problem has not been addressed so far. We propose heuristic solutions since the problem is NP-hard. Initially, we consider a number of dispatching rules commonly used for the considered objective in other scheduling environments. We identify through computational experiments the best performing dispatching rule; and then propose simulated annealing (SA) and genetic algorithms (GA) by using the best performing dispatching rule as an initial solution. This achieves at least 50% improvement in the SA and GA performances. Next, we propose enhanced versions of SA and GA and show through computational experiments that the enhanced versions provide over 90% further improvement. The performance of enhanced GA is slightly better than that of enhanced SA; however, the computation time of enhanced GA is about 10 times that of enhanced SA. Therefore, we conclude that the enhanced SA outperforms the enhanced GA.

Minimizing total tardiness in no-wait flowshops

Department of Industrial and Management Systems Engineering, College of Engineering and Petroleum, Kuwait University, P.O. Box 5969, Safat 13060, Kuwait, Fax: +965 2481 6137

Foundations of Computing and Decision Sciences

{"article-title":"Minimizing total tardiness in no-wait flowshops"}

We address the m-machine no-wait flowshop scheduling problem; where the objective is to minimize total tardiness. To the best of our knowledge, the considered...

Minimizing total tardiness in no-wait flowshops

Published Online: Oct 01, 2012

Page range: 149 - 162

DOI: https://doi.org/10.2478/v10209-011-0009-6

Keywords
No-wait, scheduling, flowshop, total tardiness.

This content is open access.

Minimizing total tardiness in no-wait flowshops

Published Online: Oct 01, 2012

Page range: 149 - 162

DOI: https://doi.org/10.2478/v10209-011-0009-6

KeywordsNo-wait, scheduling, flowshop, total tardiness.

This content is open access.

Keywords
No-wait, scheduling, flowshop, total tardiness.