COVERT Based Algorithms for Solving the Generalized Tardiness Flow Shop Problems

Document Type : Research Paper


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

2 School of Management, Tabatabaei University, Iran


Four heuristic algorithms are developed for solving the generalized version of tardiness flow shop problems. We consider the generalized tardiness flow shop model with minimization of the total tardiness as its performance measure. We modify the concept of cost over time (COVERT) for the generalized version of the flow shop tardiness model and employ this concept for developing four algorithms. The efficiency of the developed algorithms is then tested through extensive computational experiments and the results will be presented.


Main Subjects

[1] Ahmadi J.H., Ahmadi R.H., Dasu S., Tang C.S. (1992), Batching and scheduling jobs on batch and
discrete processors; Operations Research 40(4); 750-763.
[2] Allahverdi A., Al-Anzi F.S. (2002), Using two-machine flow shop with maximum lateness objective to
model multimedia data objects scheduling problem for WWW applications; Computers and
Operations Research 29(8); 971-994.
[3] Armentano V.A., Ronconi D.P. (1999), Tabu search for total tardiness minimization in flow shop
scheduling problems; Computers & Operations Research 26(3); 219-235.
[4] Baker K.R. (1974), Introduction to Sequencing and Scheduling; John Wiley & Sons Inc., New York.
[5] Baker K.R. (1984), Sequencing rules and due date assignments in a job shop; Management Science
30(9); 1093-1104.
[6] Baker K.R., Schrage L.E. (1987), Finding an optimal sequence by dynamic programming: an extension
to precedence-related tasks; Operations Research 26; 111-120.
[7] Baker K.R., Schrage L.E. (1990), Sequencing with earliness and tardiness penalties: a review;
Operations Research 38; 22-36.
[8] 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.
[9] Carroll D.C. (1965), Heuristic sequencing of jobs with single and multiple components; Ph.D.
Dissertation, Sloan School of Management, MIT, Mass.
[10] Etiler O., Toklu B., Atak M., Wilson J. (2004), A generic algorithm for flow shop scheduling
problems; Journal of Operations Research Society 55(8); 830-835.
[11] Faaland B., Schmitt T. (1987), Scheduling tasks with due dates in a fabrication/assembly process;
Operations Research 35(3); 378–388.
[12] Ghassemi-Tari F., Olfat L. (2004), Two COVERT based algorithms for solving the generalized flow
shop problems; Proceedings of the 34th International Conference on Computers and Industrial
Engineering 34; 29-37.
[13] Ghassemi-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.
[14] Glover F. (1994), Tabu search fundamentals and uses; Working paper; University of Colorado,
[15] Hall N.G., Posner M.E. (1991), Earliness-tardiness scheduling problems, I: Weighted deviation of
completion times about common due date; Operations Research 39; 836-846.
[16] Hall N.G., Posner M.E. (1991), Earliness-tardiness scheduling problems, II: Deviation of completion
time about common due date; Operations Research 39; 847-856.
[17] Hall N.G., Posner M.E. (2001), Generating experimental data for computational testing with machine
scheduling applications; Operations Research 49; 854-865.
[18] Kanet J. (1981), Minimizing the average deviation of job completion times about a common due date;
Naval Research Logistics Quart. 28; 643-651.
[19] Karimi A. (1992), Optimal cycle times in multistage serial systems with set-up and inventory costs;
Management Science 38(10); 1467–1481.
[20] Kim Y.D. (1993), Heuristics for flow shop scheduling problems minimizing mean tardiness; Journal
of Operations Research Soc. 44(1); 19-28.
[21] 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.
[22] Lee I. (2001), Artificial intelligence search methods for multi-machine two-stage scheduling with due
date penalty, inventory, and machining costs; Computers & Operations Research 28(9); 835-852.
[23] Mosheiov G. (2003), Scheduling unit processing time jobs on an m-machine flow shop; Journal of the
Operations Research Society 54(4); 437-441.
[24] Rachamaduagu R.V., Morton T.E. (1982), Myopic heuristic for the single machine weighted tardiness
problem; Working paper Gs. IA, Carnage Mellon University 38; 82-83.
[25] Rachamaduagu R.V. (1984), Myopic heuristic in open shop scheduling; Proceedings of the 14 Annual
Pittsburgh Conference on Modeling & Simulation; 14; 1245-1250.
[26] Sapar H., Henry M.C. (1996), Combinatorial evaluation of six dispatching rules in dynamic twomachine
flow shop; International Journal of Management Science 24(1); 73-81.
[27] Suliman S.M.A. (2000), A two-phase heuristic approach to the permutation flow shop scheduling
problem; International Journal of Production Economics 64(1-3); 143-152.
[28] Sundararaghavan P., Ahmed A.U. (1984), Minimizing the sum of absolute lateness in single-machine
and multi-machine scheduling; Naval Research Logistics Quart 31; 325-333.
[29] Vepsalainen A.P.J., Morton T.E. (1987), Priority rules for job shops with weighted tardiness costs;
Management Science 23(8); 1035-1047.
[30] 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