A Set of Algorithms for Solving the Generalized Tardiness Flowshop Problems

Document Type : Research Paper


1 Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran

2 School of Management, Alameh-Tabatabie University, Tehran, Iran


This paper considers the problem of scheduling n jobs in the generalized tardiness flow shop problem with m machines. Seven algorithms are developed for finding a schedule with minimum total tardiness of jobs in the generalized flow shop problem. Two simple rules, the shortest processing time (SPT), and the earliest due date (EDD) sequencing rules, are modified and employed as the core of sequencing determination for developing these seven algorithms. We then evaluated the effectiveness of the modified rules through an extensive computational experiment.


Main Subjects

[1] Baker K.R. (1974), Introduction to Sequencing and Scheduling; John Wiley & Sons, Inc.; New York,
ISBN 0-471-04555-1.
[2] Bilge U., Kirac F., Kurtulan M., Pekgun P. (2004), A tabu search algorithm for parallel machine total
tardiness problem; Computers & Operations Research 31(3); 397-414.
[3] Bulbul k., Kaminsky P., Yano C. (2004), Flow Shop scheduling with earliness, tardiness, and
intermediate inventory holding cost; Naval Logistics 51; 407-445.
[4] Carroll D.C. (1965), Heuristic sequencing of jobs with single & multiple components; Ph.D.
dissertation, Sloan School of Management; Massachusetts Institute of Technology, Mass.
[5] Chio S.W., Lee G.C., Kim Y.D. (2005), Minimizing total tardiness of orders with reentrant lots in a
hybrid flow shop; International Journal of Production Research 43(11); 2149-2167.
[6] Ghessemi-Tari F., Olfat L. (2004), Two COVERT based algorithms for solving the generalized flow
shop problems; Proceeding of the 34th International Conference on Computers and Industrial
Engineering; 29-37.
[7] Ghessemi-Tari F., Olfat L. (2007), Development of a set of algorithms for the multi-projects
scheduling problems; Journal of Industrial and Systems Engineering 1(1); 11-17.
[8] Gupta N.D., Kruger K., Lauff V., Werner F., Sotskov Y.N. (2002), Heuristics for hybrid flow shops
with controllable processing times and assignable due dates; Computers & Operations Research
29(10); 1417-1439.
[9] Lauff V., Werner F. (2004), On the complexity and some properties of multi-stage scheduling
problems with earliness and tardiness penalties; Computers & Operations Research 31(3); 317-345.
[10] Lee G.C., Kim Y.D. (2004), A branch and bound for a two stage hybrid flow shop scheduling problem
minimizing total tardiness; International Journal of Production Research 42(22); 4731-4743.
[11] Lin H.T., Liao C.J. (2003), A case study in a two-stage hybrid flow shop with setup time and dedicated
machines; International Journal of Production Economics 86(2); 133-143.
[12] Takaku K., Yura K. (2005), Online scheduling aiming to satisfy due date for flexible flow shops;
JSME International Journal Series C 48(1); 21-25.
[13] Yeh W., Allahverdi A. (2004), A branch and Bound algorithm for the three machine flow shop
scheduling problem with bi-criteria of make-span and total flow time; International Transaction in
Operations Research 11(30); 323-327.