Development of a Set of Algorithms for the Multi-Project Scheduling Problems

Document Type : Research Paper


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

2 School of Management, Tabtabaei University, Iran


In this paper, the problem of determining the best schedule for a set of projects has been modeled in the form of a generalized tardiness flowshop (GTF) problem. We develop a set of heuristic algorithms for minimizing the total tardiness of jobs in a GTF problem. In the generalized version of tardiness flowshop problems, a job is considered to be a collection of operations and there is a due date associated with the completion of each operation on each machine. Four algorithms based on the concept of “apparent tardiness cost” (ATC) are developed for solving the GTF problem. The relative effectiveness of the developed algorithms will then be evaluated through an extensive computational experiment.


Main Subjects

[1] Allahverdi A. (2004), A new heuristic for m-machine flow shop scheduling problem with bicriteria
of makespan and maximum tardiness; Computers & Operations Research 31(2); 157-180.
[2] Baker K.R., Bertrand J.W.M. (1982), A Dynamic priority rule for sequencing against due dates;
Journal of Operational Management 3(1); 37-42.
[3] Baker K.R. (1984), Sequencing rules & due date assignments in a job shop; Management Science
30(9); 1093-1104.
[4] 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.
[5] Carroll D.C. (1965), Heuristic sequencing of jobs with single & multiple components, Ph.D.
dissertation, Sloan School of Management, MIT, Mass.
[6] Chakravarthy K., Rajendran C. (1999), A heuristic for scheduling in a flowshop with the bicriteria of
makespan and maximum tardiness minimization; Production planning and control, 10(7); 701-714.
[7] 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.
[8] 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.
[9] Ghessmi-Tari F., Olfat L. (2004), Two COVERT based algorithms for solving the generalized flowshop
problems; Proceedings of the 34th International Conference on Computers and Industrial
Engineering, 29-37.
[10] 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.
[11] 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-
[12] Lee L. (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-
[13] 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.
[14] Linn R., Zhang W. (1999), Hybrid flowshop scheduling: a survey; Computers & Industrial
Engineering 37( 1&2); 57-61,
[15] Mosheiov G. (2003), Scheduling unit processing time jobs on an m-machine flowshop; Journal of
the Operations Research Society 54( 4); 437-441
[16] Olfat L. (1998), Development of a set of algorithms for flowshop tardiness problems, Ph.D.
dissertation, School of Management, University of Tehran, Tehran, Iran.
[17] Parthasarathy S., Rajendran C. (1998), Scheduling to minimize mean tardiness and weighted
tardiness in flowshop and flowline-based manufacturing cell; Computers & Industrial Engineering
34(2); 431-546.
[18] Rachamaduagu R.V., Morton T.E. (1982), Myopic heuristic for the single machine weighted
tardiness problem, working paper #38-82-83, GsIA, Carnegie Mellon University.
[19] Rachamaduagu R.V. (1984), Myopic heuristic in open shop scheduling, modeling & simulation,
Proceedings of the 14 Annual Pittsburgh Conf., 1245-1250.
[20] Sapar H., Henry M.C. (1996), Combinatorial Evaluation of six dispatching rules in dynamic two
machine flowshop; International Journal of Management Science 24,( 1); 73-81.
[21] Vepsalainen A.P.J., Morton T.E. (1987), Priority rules for job shops with weighted tardiness costs;
Management Science 23(8); 1035-1047.
[22] 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(3); 323-332.