No-wait flowshop scheduling problem to minimize the number of tardy jobs

Aldowaisan T. A., Allahverdi A.

International Journal of Advanced Manufacturing Technology, vol.61, no.1-4, pp.311-323, 2012 (SCI-Expanded) identifier

  • Publication Type: Article / Article
  • Volume: 61 Issue: 1-4
  • Publication Date: 2012
  • Doi Number: 10.1007/s00170-011-3659-x
  • Journal Name: International Journal of Advanced Manufacturing Technology
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.311-323
  • Keywords: Flowshop, Heuristic, No-wait, Pair-wise exchange, Scheduling, Simulated annealing, Tardy jobs
  • Gazi University Affiliated: No


This research addresses the m-machine no-wait flowshop scheduling problem with the objective of minimizing the number of tardy jobs. The problem is known to be NP-hard even for the two machines, and literature reveals that no heuristics have been developed for this problem. In this paper, we propose an efficient heuristic based on simulated annealing, where we first adapt the single-machine optimal algorithm to our problem to develop two new heuristics, NOTA and NOTM. An improved simulated annealing heuristic, called SA-GI, is then developed by feeding the best performing heuristic among NOTA, NOTM, and EDD into the simulated annealing algorithm. A second proposed heuristic, called SA-IP, further improves the SA-GI solution by using insertion and pair-wise exchange techniques. Based on the computational experiments, the overall relative percentage errors of the heuristic SA, SA-GI, and SA-IP are 8.848, 8.428, and 0.207, respectively. The computational times of the three heuristics are close to each other, and the largest average time is less than one second, and hence, the computational time is not an issue. Therefore, the heuristic SA-IP is the best one. © 2011 Springer-Verlag London Limited.