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

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



Problems







Farhad Ghassemi-Tari1*, Laya Olfat2







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







(ghasemi@sharif.edu)



2 School of Management, Tabtabaei University, Iran







(l_olfat@yahoo.com)







ABSTRACT







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.







Keywords: Generalized tardiness flowshop; Multi-project scheduling; Intermediate due date;



Apparent tardiness cost







1. INTRODUCTION







In this paper we consider the problem of determining the best schedule for a set of projects to



minimize the total tardiness of the project’s deliverable tasks. It is assumed that, the tasks



precedence structure in each project is in the form of a “linear precedence structure”. The flowshop



model is the most appropriate type of model for embodying this type of precedence structure. We



therefore model this problem in the form of a tardiness flowshop problem. There is however, a



major distinction between the traditional flowshop models with the model we are proposing for our



multi-project scheduling problem. In traditional flowshop models with tardiness criterion, there is a



single due date for each job or more precisely for the last operation of each job. In our project



scheduling problem, however, there are several deliverable tasks for each project and a due date is



assigned for each deliverable task. Therefore we are facing a tardiness flowshop model with



intermediate due dates which we call the “generalized tardiness flowshop” (GTF) model. This



nomination is due to the fact that, if we assign large values to the intermediate due dates, we obtain



a traditional model as a special version of our proposed generalized tardiness flowshop model.







While considerable research has been devoted to the problem of minimizing the makespan, very



little work is reported on minimizing the total tardiness of jobs on a permutation flowshop



(Ghassemi and Olfat, 2004). Even in those research efforts considering different variants of the total







*Corresponding Author





----------------------- Page 2-----------------------



24 Ghassemi-Tari and Olfat







tardiness measures none has been found to address the problem of scheduling jobs in a flowshop



system with intermediate due dates.







Although a limited number of studies have addressed the tardiness criterion in flowshop scheduling



problems, there are some valuable concepts in tardiness criterion of single machine, and job shop



sequencing models which can be modified and used in flowshop problems (Baker and Bertrand,



1982). Among these studies is the earlier work of Carroll (1965) who presented a dynamic rule



called cost over time (COVERT) for a single machine and job shop sequencing problems to



minimize the total weighted tardiness of jobs. Under this rule the degree of criticality of jobs were



used for determining the jobs sequence. Rachamaduagu and Morton (1982) introduced a rule called



apparent tardiness cost (ATC) for the single machine sequencing with the total weighted tardiness



criterion. Later Rachamaduagu (1984) conducted an experiment for comparing the ATC rule with



COVERT. In this experiment he applied both rules to the single machine, parallel machine and



flowshop sequencing problems, and concluded that ATC is a more efficient rule than COVERT in



obtaining the solution. Vepsalainen and Morton (1987) reached the same conclusion when they



used both rules, as well as some other rules in solving job shop sequencing problems. They



considered job shop problems with tight due dates, loose due dates and different workloads and



concluded that ATC performed better in all these cases and COVERT had the second best



performance among all the rules the employed.







Baker (1984) conducted a research to evaluate different sequencing rules in job shop scheduling



problems. He classified several rules in three groups, namely, slack based, critical ratio based, and



the rule based on the time gap between completion of partially scheduled jobs and their associated



due dates. He then evaluated different rules for each group. As the result he concluded the slack



based rules had a lower performance, and among the rules in other two scheduling groups, the



operation-oriented rules perform better than job-oriented rules. Based on the concepts of ATC,



COVERT, and the critical ratio indices Olfat (1998) developed several heuristic rules for flowshop



tardiness problems. In the same work, she also developed a set of rules, called ranking rules, by



which a schedule is developed for each machine and jobs are ranked according to their positions in



a sequence. The total rank of the jobs is then used to determine the final permutation schedules. She



compared the developed rules through conducting an extensive computational experiment.







Later, Ghassemi-Tari and Olfat (2004) proposed two COVERT based algorithms for solving the



generalized tardiness flowshop model. They conducted an extensive computational experiment for



comparing the efficiency of their developed algorithms. Sapar and Henry (1996) evaluated six



scheduling rules for two machine flowshop problems with the average tardiness criterion. Among



the rules they considered, the modified due date rule (MDD) was reported to be superior under all



variants of their experimental conditions. There have been some other related studies considering



tardiness criterion, among which one can cite the works conducted by Lin and Zhang (1999) and



Lee (2001).







There have also been some limited research efforts considering special versions of flow shop



models. A hybrid flowshop scheduling model is one special type of the flowshop models. In a



hybrid flowshop, one considers a shop in which there are serial stages, each with identical parallel



machines. Lee and Kim (2004) suggested a branch and bound algorithm for a two-stage hybrid



flowshop scheduling problem minimizing the total tardiness. In their study a two-stage hybrid



flowshop scheduling problem is considered with the objective of minimizing the total tardiness of



jobs.





----------------------- Page 3-----------------------



Development of a Set of Algorithms for the … 25







In another research attempt, Choi et al, (2005) considered the total tardiness scheduling problem for



the hybrid flowshop in which a set of orders with reentrant lots were scheduled. In their model, each



order is composed of multiple lots with the same due date, and each lot can be processed on any one



of parallel machines at each stage. In addition, they considered a situation in which lots of certain



orders have to visit some stages twice. They proposed a set of heuristic algorithms with some



supporting computational experiments, to reveal that the suggested algorithms perform better than



the well-known dispatching rules for various scheduling problems. There are some other works



dealing with the tardiness hybrid flowshop, such as the works conducted by Janiak et al, (2005), Lin



and Liao (2003), and Gupta et al, (2002).







The bi-criteria flowshop model is another type of special flowshop models. Allahverdi (2004)



proposed a heuristic algorithm for the flowshop scheduling problem with bi-criteria of makespan



and tardiness. A weighted sum of makespan and maximum tardiness are used as the objective to be



minimized. In his paper, two types of the problem were addressed. In one a limit was assigned to



the maximum tardiness while in the second type this constraint was relaxed. A new heuristic was



proposed and compared to two existing heuristics. A computational experiment was performed and



the results indicated that the proposed heuristic was much better than the existing ones.







In a similar study, Parthasarathy and Rajendran (1998) proposed a heuristic for the problem of job



scheduling in flowshop and flowline-based manufacturing cells with the bi-criteria of minimizing



mean makespan and mean tardiness of jobs. They developed a heuristic algorithm, based on the



simulated annealing technique. They then evaluated their proposed algorithm against the existing



heuristics and showed that the proposed algorithm performed better than the existing heuristics.



Later Chakravarthy and Rajendran (1999) developed the bi-criteria of makespan and maximum



tardiness minimization heuristic for a flowshop model. Their developed heuristic was also based on



the simulated annealing technique. They performed a computational experiment for evaluating the



proposed heuristic against the existing heuristic and the computational evaluation revealed that the



proposed heuristic performed better than the existing ones.







Some other tardiness scheduling problems have considered batch processing of jobs; the related



works have been presented by (Yeh and Allahverdi, 2004; Etiler et al, 2004; Bilge et al, 2004).







Mosheiov (2003) considered the problem of batch processing in which two elements of “job



identical processing times” and “job-dependent weights” were combined in an m-machine flow



shop scheduling model. A common due date was considered for the jobs. He considered the (just in



time) objective of minimizing the maximum earliness/tardiness cost. He then introduced a



polynomial time solution approach for the proposed problem.







Thorough review of literature has shown that no single research effort, considering the flowshop



tardiness problem with intermediate due dates, has been reported to date.







In this paper four heuristic algorithms based on the concept of Apparent Tardiness Cost (ATC) are



developed for tardiness minimization of flowshop scheduling problems with intermediate due dates.



We then evaluate the effectiveness of the four proposed algorithms using an extensive experimental



study.







2. NOMENCLATURE







The following notations are used throughout this manuscript:



n: Number of jobs





----------------------- Page 4-----------------------



26 Ghassemi-Tari and Olfat







m: Number of operations or machines



p ij: Processing time for operation j of job i.



dij; Due date for operationj of job i.



rij: The total processing time of job i on machines 1,2,…, and j-1.



t : The completion time of thej th operation of the job which is sequenced directly before job



ij







i on machinej .



Cij: Completion time of job i on machinej .



TT: Total tardiness of a schedule



TT(S): Total tardiness of schedule S



j j







TT : Total tardiness of a schedule of all jobs on machinej.



j







Tk(S): Tardiness of job k in schedule S



Aj : An ordered set of partially scheduled jobs on machine j.



B: A set of unscheduled jobs (complement of Aj ).



S : A permutation schedule, in which jobs are sequenced according to the order of jobs



j







determined on machinej.







3. THE MODEL







Considering n projects as n jobs, m activities in each project as m operations, and m research teams



as m machines we can build a flow shop model for our multi-project scheduling problem. We



assume that activities in each project have a special precedence structure. In particular, each activity



after the first has exactly one direct predecessor and each activity before the last has exactly one



direct successor. Figure 1 illustrates a pure flow- shop model for a multi-project scheduling problem



when the precedence of the project tasks is structured according to a linear precedence structure or



equivalently as a flowshop model. The pure flowshop consists of exactly m different machines and



each job consists of exactly m operations, each of which requires a different machine.







Input







Machine 1 Machine 2 Machine 3 Machine m



or Task 1 or Task 2 or Task 3 or Task m







Output







Figure 1. Project tasks flow in a pure flowshop







In the general case, jobs may require fewer than m operations, or their operations may not always



require adjacent machines, or the initial and/or final operations may not always occur at machine 1



and m. Nevertheless, the flow of work is still unidirectional and we can represent the general case as



a pure flowshop in which some of the operation times are zero. Figure 2 represents the flow of the



project tasks in a more general flowshop model.





----------------------- Page 5-----------------------



Development of a Set of Algorithms for the … 27







Input Input Input Input







Machine 1 Machine 2 Machine 3 Machine m



or Task 1 or Task 2 or Task 3 or Task m







Output Output Output Output







Figure 2. Project tasks flow in a general flowshop







Thus each project requires a specific sequence of activities to be carried out for the project to be



completed, and there is a due date associated with the completion of each activity. From now on we



refer to each project as a job each activity as an operation, and each research team or department as



a machine. Therefore we have a flowshop model with n jobs, each having m operations and m



machines for performing m operations of each job. The flowshop is characterized by a flow of work



that is unidirectional. In other words, a flowshop model consists of a natural machine order and



hence the operation j of job i is performed on machine j . It should be noted that some of jobs may



require fewer than m operations, that their operations may not always require adjacent machines in



the same order. For these jobs we assume there are also m operations where the corresponding



processing times for the missing operations can be assumed to have a zero value. We propose our



algorithm for the generalized tardiness flow shop model under the following conditions:







- A set of m-operations, n-jobs is available for processing at the beginning of scheduling



time.



- Setup times for the operations are sequence-independent and are included in processing



times.



- Operation processing times (p ij) are known and are deterministic.



- There is a corresponding due date for completion of each operation (dij).



- As long as there is a job, m-machines are available for processing the jobs.



- Individual job operations can not be preempted.







As it is common in sequencing we use the bracket symbol for specifying the position of a job in a



sequence. Therefore [k]=i indicates that job i has the kth position in a sequence. We now present the







developed algorithm for minimizing the total tardiness of flowshop scheduling problem in which



the total tardiness is defined as the summation of the tardiness of the jobs on the last machine as



well as the tardiness of the jobs on the intermediate machines.







To present a mathematical programming formulation for the proposed problem, we consider a set of



n jobs, each having m operations to be performed on m different machines with a unidirectional



precedence structure. In this case we can number machines according to the operation numbers of



each job. Then we will have a one to one correspondence in operation numbers and machine



numbers. Therefore as in the case of the "pure' flowshop model, the j th operation of each job is



performed on thej th machine for all values ofj=1, 2…m .





----------------------- Page 6-----------------------



28 Ghassemi-Tari and Olfat







We intend to find a permutation schedule to minimize the total tardiness. To do so let xj denote the



i



variable indicating the starting time of thej th operation of job i. This problem then can be formulated







as a mathematical programming model as follows:







n m



min TT ??max( xj =+ p - d ,0)



i ij ij



i 1 j 1







Subject to xj - xj = p for k << l , j 1,2,..n



l k kj







The difficulty in this formulation arises from the fact that the direct precedence relation (k<


requires that all permutations of the jobs to be considered in solving this mathematical



programming model. Solving this mathematical programming model, for large values of n and/or m



(in a practical size problem), leads to computational complexity due to the exponentially growth of



solution space. Therefore the only solution approach for practical cases is the use of a heuristic



approach. In the following section we describe the development of the heuristic algorithms for this



problem.







4. DEVELOPMENT OF ALGORITHMS







In this section we present the heuristic algorithms we developed for solving flowshop scheduling



problems with the total tardiness criterion, while considering a tardiness for each operation of each



job completed after its associated due date. The developed algorithms are dynamic procedures by



their nature of producing the final schedule. In contrast to the static procedures by which a schedule



is produced by m-jobs-at-a-time sequencing rules, a dynamic procedure produces a schedule using



one job at a time sequencing rules. In the latter case information regarding completion times of the



scheduled jobs is used for selecting the next job to be sequenced.







The developed algorithms are based on the concept of the apparent tardiness cost (ATC).



The ATC is an index that has been used for the dynamic sequencing rules in single machine



scheduling problems. Based on this index, we develop four sequencing algorithms for solving our



flow shop scheduling problem, which we name as AT1 through AT4 algorithms.







Using the concept of pseudo random number generation and by employing the above mentioned



formulas we generated the experimental test problems. By assigning different values to m, n, and



TF, we defined several different test problems scenarios. To reduce any bias of the generated data,



we defined a sample size (k) for the test problems and for each scenario we employed the average



value of the sample’s solutions for any further experimental analysis. In other word, for each



scenario, k test problems are generated using different seeds for the random number generation



process and by using the average value of the solutions of the test problems we compare the relative



effectiveness of the proposed algorithms. The following section summarizes the results.







5.2. Computational Results







We let R=0.02, and generated 96 scenarios through the combinations of four different values of m,



eight different values of n, and three different values of TF. For each scenario 40 test problems were



randomly generated to obtain the p ij and the dij values. For each scenario, all 40 test-problems were



solved by the proposed algorithms, to determine the average of total tardiness. We then selected the



algorithm with the minimum average of the total tardiness as the reference algorithm, and then we



determined the relative measure of effectiveness of each algorithm, by the deviations of its average



solution from the average solution of the reference algorithm.







To define the relative efficiency, we calculated the relative deviation as:







ATT - min{ATT }



i k



RAD k =× 100



i



min{ATT }



k



k







where RADi is the relative average deviation of the ith algorithm, and ATTi is the average total



tardiness of the 40 test problems solved by the ith algorithm. We then defined 96 different scenarios







by assigning 8 different values to n (n=5, n=10, n=15, n=20, n=25, n=30, n=35, n=40), 4 different



values to m (m=5, m=10, m=15, m=20), and 3 different values to TF (TF=0.1, TF=0.2, TF=0.4).



For each scenario 40 test problems were generated and solved by the developed algorithms and their



relative average deviations were calculated. Table (1) demonstrates the relative average deviation



values of the 40 test problems obtained by each algorithm according to the different values of n and



TF, when m=5. Similarly Tables (2) through (4) illustrate the relative average deviation values of



40 test problems for different scenarios when m=10, m=15, and m=20 respectively. Through these



tables it can be observed that in most cases, algorithm AT4 has the best effectiveness followed by



AT3 which has the second best effectiveness ranking among the four algorithms.







We further analyzed the relative effectiveness of the developed algorithms by comparing them in



the absence of the toughness factors (TF). To conduct this analysis, we first defined a new index by



calculating the average of the deviations over three different TF values. We then plotted a curve for



each algorithm which illustrates the variations of this index, according to the different values of n.



Figures 1 through 4 demonstrate these curves for m=5 , m=10, m=15, and m=20 respectively.



These curves reveal that, except for m=5, algorithm AT4 demonstrates a better effectiveness. It can



also be concluded that algorithm AT3 performs superbly when m=5.