Equal Processing Time Bicriteria Scheduling on Parallel Machines

Journal of Combinatorial Optimization, 8, 227–240, 2004 c 2004 Kluwer Academic Publishers. Manufactured in The Netherlands.


Equal Processing Time Bicriteria Scheduling on Parallel Machines SUBHASH C. SARIN DIVYA PRAKASH Grado Department of Industrial and Systems Engineering, Virginia Tech, Blacksburg, Virginia 24061, USA Received March 9, 2000; Revised May 4, 2004; Accepted May 7, 2004

Abstract. We consider the problem of scheduling jobs on parallel, identical machines so as to minimize a primary and a secondary criteria. All the jobs are assumed to have identical processing times. Polynomial time algorithms, that generate optimal solutions, are presented for various combinations of primary and secondary criteria. Keywords: bicriteria scheduling, parallel machines, equal processing time jobs

1.

Introduction

We consider the problem of scheduling jobs on parallel, identical machines so as to minimize a primary and a secondary criteria. All the jobs are assumed to have identical processing times. Various combinations of primary and secondary criteria are considered from among total tardiness, maximum tardiness, number of tardy jobs and weighted completion time. As a stepping stone towards the development of algorithms for the bicriteria problems, first, single criterion, parallel, identical machine, equal processing time problems are analyzed for the above mentioned criteria. The bicriteria scheduling problems are motivated by the fact that they are more meaningful from practical point of view. For instance, it is not only important to minimize the total number of tardy jobs to satisfy as many customers as possible, but also it is relevant to minimize total completion time to reduce work-in-process. An application of the parallel machine problem on hand is a flexible flow shop in which the jobs, waiting to be processed at a stage, are to be scheduled on parallel machines. Flexible flow shops occur in real life scenarios of, among others, repair facilities (Hodgson and McDonald, 1981) and semiconductor manufacturing (Wittrock, 1985). In a flow shop, when a batch of identical jobs is split into sublots for processing, it has been shown by several researchers (see e.g., Vickson and Alfredson, 1992; Potts and Baker, 1989) that the consideration of equal sublot sizes is almost as good as the use of unequal sublot sizes from the viewpoint of the performance of a schedule. This leads to the scheduling of identical processing time jobs at every stage of a flexible flow shop (containing parallel machines) which is the problem addressed in this paper. For a review of multicriteria scheduling, the reader is referred to T’kindt and Billaut (2002). Most of the work reported in this area has been on the single machine bicriteria problems. However, the parallel machine problem is different from the single machine

228

SARIN AND PRAKASH

problem due to the availability of several machines to allocate the jobs to at every period of time. As a result, the problem is to determine an appropriate subset of jobs (having different due dates and weights) to allocate to the machines at each position. As regards the single machine bicriteria problem, Chen and Bulfin (1989, 1994) have studied the case of unit processing time and have proposed algorithms to generate both the efficient (nondominated) schedules as well as the schedules that optimize the bicriteria problems in a sequential fashion. De et al. (1991) enriched the work of Chen and Bulfin (1994) by providing some clarifications on the simultaneous minimization of the criteria under consideration. Chen and Bulfin (1993) later studied the complexity of various single machine, bicriteria problems. Most of the problems in the bicriteria scheduling literature involve minimization of flow time or weighted flow time subject to a T max value. Minimization of weighted completion time subject to minimal value of T max was first considered by Smith (1956) who proposed an algorithm of complexity O(n log n). Chand and Schneeberger (1986) analyzed Smith’s heuristic algorithm and suggested some modifications. Many combinations of the problem parameters are identified for which Smith’s algorithm produces optimal result. van Wassenhove and Gelders (1980) have suggested an algorithm for the problem involving the flow time (holding cost) and maximum tardiness criteria. They used the modified due date concept and a modified Smith’s algorithm to solve this problem. This algorithm is shown to be polynomial by Hoogeveen and van de Velde (1995). Nelson et al. (1986) developed a branch and bound scheme for problems involving mean flow time, number of tardy jobs and maximum tardiness, and they developed trade-off curves to obtain efficient schedules. Nelson et al. (1986) then extended this work to optimize the above three criteria simultaneously. Daniels (1994) used preference information on an interactive basis to solve the problem of optimizing multiple criteria. For a detailed coverage of research on the single machine multiple objective sequencing problem, the reader is referred to Fry et al. (1989). Recently, Hoogeveen (1996) has presented an O(n 2 log n) algorithm to determine the trade-off curve for maximum lateness and maximum promptness, where the promptness of a job is the difference between its start time in a schedule and its target start time. Hoogeveen (1996) also determines all Pareto-optimal points in O(n 4 ) and O(n 8 ) time, respectively, for the single machine scheduling problem to minimize a function of two and three maximum cost criteria. Vairaktarakis and Lee (1995) have proposed a branch and bound algorithm to minimize total tardiness subject to minimum number of tardy jobs. Branch and bound schemes have also been used by Azizoglu and Kondacki (1991) for the total earliness and tardiness problem and by Dileepan and Sen (1991) and Sen et al. (1977) to solve the problem of optimizing total flow time and sum-squared of lateness (and range of lateness) for the single machine case. Lin (1983) presented a dynamic programming approach to simultaneously optimize total tardiness and flow time of the jobs on a single machine. Cenna and Tabucanon (1991) suggested a method to optimize mean flow time and maximum tardiness using a goal programming approach, i.e., by assigning weights to both the criteria. Sarin and Hariharan (2000) proposed a heuristic to optimize number of tardy jobs under the constraint of maximum tardiness for the two machine case. Cheng (1991) developed a solution methodology for minimizing the flow time and missed due dates for the single machine problem. Cheng (1990) also proposed a better solution procedure by using penalty functions for the criteria of job completion times and total flow time. Ramesh and

EQUAL PROCESSING TIME BICRITERIA SCHEDULING

229

Cary (1989) suggested an approach for efficient job shop scheduling under the criteria of the number of tardy jobs, mean tardiness and average completion time. Grabot and Geneste (1994) have used an approach based on fuzzy sets to suggest dispatching rules similar to SPT for multi-criteria problems. From a practical point of view, Bausch (1992) used a branch and bound approach to solve the problem for steel plants that involves a single machine bicriteria (process based criterion) problem. Pickens and Hoff (1991) have used fuzzy goal programming approach for a similar problem regarding forest harvest scheduling. The single criterion, equal processing time problems are rather straightforward to model. The formulations of the bicriteria problems are similar to those of the single criterion problems but involve additional requirements due to the fact that the primary objective is not to be violated. Consequently, the bicriteria problem is solved in two steps. First, the primary criterion is optimized followed by the optimization of the secondary criterion subject to the primary objective function value. The primary and secondary criteria problems can also be solved in one step by combining the two criteria into one objective function, with appropriate weights associated with each. By using suitable values of weights, the primary and secondary objectives can be achieved. However, the linear relaxations of the formulations of the primary and secondary problems, as well as that of the combined problem, result in highly fractional solutions. Therefore, these model formulations need to be solved as integer programs which, expectedly, become computationally prohibitive with increase in their size. As a result, in this paper, we analyze each problem situation individually and develop an efficient algorithm for its solution. In the sequel, we first introduce the assumptions made and the notation used in the paper. The single criterion, parallel machines, equal processing time problems are then discussed followed by the bicriterion problems. 2.

Assumptions and notation used

We make the following assumptions: (1) the jobs are available at time zero and are independent of each other, (2) no preemption is allowed, and (3) the machines are identical in all respects and are available all the time. The following notation will be used in the sequel. i di Ci Ti NT T max N M j k wi

designates a job, where i = 1, 2, 3, . . . , N due date of job i (it need not be integer) completion time of job i tardiness of job i (which is nonnegative lateness, i.e., max (Ci − di , 0)) number of tardy jobs maximum job tardiness number of jobs to be scheduled number of machines available N + location of job i on machine k, where j = 1, 2, 3, . . . , [ M ] , and [ ]+ denotes N smallest integer large than [ M ] machine on which a job i is assigned at position j, where k = 1, . . . , M importance factor (weight) of job i

230

SARIN AND PRAKASH

Since we are considering the situation of jobs requiring equal processing times, for analysis purposes, and without loss of generality, we can assume processing time of one unit for every job. 3.

Parallel machines, equal processing time, single criterion problems

The criteria that we consider in our analysis include T max, total tardiness, number of tardy jobs (NT) and weighted flow time. First, consider the criteria of T max and Total Tardiness. Intuition would dictate the use of the earliest due date (EDD) order for allocating the jobs to the first available machine in order to solve for both of these due date related criteria. Indeed, this procedure generates the optimal schedule for the T max and total tardiness criteria. For future reference, this EDD based allocation procedure is designated as Algorithm A1. It can formally be presented as follows: Algorithm A1 (Minimization of T max and total tardiness) Step 1. Arrange the jobs in the increasing order of their due dates; break ties arbitrarily. Step 2. Allocate the next job in sequence to the next available position. If more than one position is available, break the tie arbitrarily. Remark 1 1 .

Algorithm A1 minimizes:

a. T max, and b. total tardiness. Consider next the criterion of number of tardy jobs (NT). Observation 1. If the jobs are allocated in the EDD order first to, say, machine k and then to machine
(see figure 1), and a job i
, allocated to machine
, is tardy, then a job

Figure 1.

Relationships between the jobs located at identical locations on different machines.

EQUAL PROCESSING TIME BICRITERIA SCHEDULING

231

Figure 2. Schedules with NT = 1 and NT = 2 (with the late jobs appearing at the same location number on different machines).

i, allocated to machine k at the identical position to that of job i
on machine
, is also tardy. This follows from the fact that di
≥ di . As the processing times of all the jobs are equal, this observation implies that if a job is late on a machine and there are other jobs ending at the identical positions on earlier machines, then all of these jobs on previous machines are also late. Moreover, if only one job is late then that job must appear on the first machine of the order in which the jobs are allocated to them. This is depicted in figure 2. Observation 2. If the EDD allocation of the jobs to the machines results in NT ≤ m and all the late jobs are located at identical locations on all the machines, then the schedule is optimal. This follows by the fact that moving a late job to any other position does not decrease the number of late jobs. Next, we present an algorithm, designated Algorithm A2, that achieves minimum NT. Algorithm A2 (Minimization of the number of tardy jobs) Step 1. Arrange the jobs in the EDD order. Step 2. Allocate the next job in sequence to the next available position if the job is early; otherwise, put the job in a late set L. Step 3. Allocate the jobs in L, one by one, to the earliest available machine; stop. Remark 2.

Algorithm A2 minimizes the total number of tardy jobs.

For the criterion of weighted completion time, the weighted smallest processing time (WSPT)2 rule gives the optimal schedule as is summarized below.

232

SARIN AND PRAKASH

Remark 3. The WSPT schedule, in which the jobs are allocated to the earliest available location on the machines in WSPT order, minimizes the weighted completion time.

4.

Parallel machines, equal processing time, bicriteria problems

Next, we address the bicriteria problems. Various combinations of the criteria discussed above are considered as primary and secondary criteria. As alluded to earlier, the approach used is similar to the sequential approach of goal programming. The primary criterion is optimized first, and then the secondary criterion is optimized constrained by the objective function value of the primary criterion. This is a two step process of which the first step is already discussed in Section 3. We designate the primary criterion as z 1 , the secondary criterion as z 2 , and the bicriteria objective function as z 2 /z 1 . Total tardiness/T max Remark 4. Algorithm A1 optimizes the total tardiness/T max as well as the T max/total tardiness bicriteria problems. This follows from the fact that Algorithm A1 optimizes both the T max and the total tardiness criteria simultaneously (by Remark 1). Next, we make an observation that will be useful in the subsequent discussion. Observation 3. In the EDD order of allocating jobs to the machines, if the immediately preceding job i of any late job, say j, is not late, then the due date of job j is not less than its start time and is strictly less than its completion time in that schedule. This is depicted in figure 3 for the cases when i and j are on the same or different machines, and it follows from the definition of lateness and Observation 1.

Figure 3.

Different locations of a late job j and its preceding job i.

EQUAL PROCESSING TIME BICRITERIA SCHEDULING

233

NT/T max The algorithm for the NT/T max problem is presented next. Subsequently, we show that this algorithm generates an optimal solution. Algorithm A3 (Optimization of the number of tardy jobs given T max) Step 1. Allocate the jobs using Algorithm A1. Let F be the set of jobs that are fixed at specified locations. Initially, set F = ∅. Step 2. Determine T max. If T max ≤ 1, stop; else, go to Step 3. Step 3. Pick the first late job i, i ∈ / F. If none exists, then stop; else go to Step 4. Step 4. Put job i in a location that is as late as possible without violating T max. Job i is now said to be fixed at that location. Break the tie using EDD if there are more than one fixed job. Update set F, F = F + {i}. Arrange the remaining jobs using A1, and go to Step 3. Theorem 1. Algorithm A3 generates optimal solution for the NT/T max bicriteria problem. Proof of Theorem 1: Let S be the schedule obtained by Algorithm A3 and S
be the optimal schedule. We prove the optimality of S by transforming S
to S without affecting its objective function value. Starting from the last position and moving forward, let these schedules S and S
be identical from position T + 1 until the end, and T be the first position where they differ. Let a job i occupy the T th position in S while a job j(= i) occupy the same position in S
. Also, let Q T be the set of jobs from those in the first T positions of S (or S
) that satisfy the optimal T max value at T . If there exists a k ∈ Q T such that it is not late when processed at T , then job i is such a job in S. In that case, in S
, job i must occupy an earlier position as j = i and schedules S and S
are identical from positions T + 1 until the end. Now, if jobs i and j are switched in S
, job i will remain early and S
cannot get any worse as job j is moving to an earlier position. In case such a job k ∈ Q T does not exist and all the jobs in Q T are late when processed in period T , let job i be the EDD job from those in Q T . If jobs i and j are switched in S
, it will not make S
any worse as both of them will remain late at T . Thus, in either case, schedule S
is transformed, as a result, to become identical to S from positions T until the end without worsening it. Designate this transformed S
by S

. Determine the next position T
, moving backward from T , at which the jobs in S and S

are different. Following the above argument, S

can be modified by switching the job in its position T
with the job that occupies position T
of S, from an earlier position in S

, without worsening S

. Call this schedule S


. Once again, the schedules S and S


are identical from positions S

until the end. By repeating the same argument, S
is transformed to S without worsening it. Weighted completion time/T max An algorithm (designated A4) for this case is presented next.

234

SARIN AND PRAKASH

Algorithm A4 (Optimization of weighted completion time given T max) Step 1. Calculate the T max value using Algorithm A1. Step 2. Arrange all the jobs in the WSPT order and assign them to the earliest available machine. Let F be a set of jobs fixed at specified locations. Initially, set F = ∅. Step 3. Pick the first late job i ∈ / F that violates the primary criterion. If none exists, then stop; else, go to Step 4. Step 4. Advance the job picked in Step 3 and place it at the latest possible location without violating the T max value. If a job has already been assigned to that location, then use the WSPT rule to break the tie. Set F = F + {i}. Consider the jobs that are not fixed, and go to Step 2. Theorem 2.

Algorithm A4 optimizes weighted completion time/T max.

Proof of Theorem 2: Let S
be an optimal schedule. First note that the value of T max obtained as a result of Algorithm A1 is the best possible. Hence, S
must have this value of T max as well. Next, we show that S
can be transformed to the schedule obtained by Algorithm A4 without worsening it. Consider the first job of S
on the first machine. Clearly, the tardiness of this job must be less than or equal to T max. Consider the first two jobs of S
on the first two machines. Arrange them in the WSPT order. If T max is not violated, keep them in the WSPT order. Otherwise, fix the job, that violates T max in the second position, at the first position (first job on the first machine). Note that one of these two cases must occur as S
is optimal. If a job is fixed, include that in set F; initially F = {∅}. Next, consider the first three jobs and so on. Let this process has progressed to the nth job and the last fixed job be k; initially we can assume k to be a dummy job. Arrange the jobs k + 1, . . . , n in the WSPT order. If the last of these jobs (on some machine) violates T max, then move it to the latest location,
, such that T max is not violated. Call it job
. Add it to F. Designate job
by k. In the event that none of the jobs k + 1, . . . , n, arranged in the WSPT order, violate T max, increment the set to n + 1. Continue until all N jobs are considered. The resultant schedule is identical to S, the one obtained by Algorithm A4 and consists of a set of jobs that is fixed while the remaining jobs are in the WSPT order. NT/total tardiness Algorithm A5 is presented next for these criteria. Algorithm A5 (Optimization of number of tardy jobs given total tardiness) Step 1. Arrange all the jobs using Algorithm A1. Let L be the set of late jobs in the current schedule. Initialize a set of jobs, SJ = ∅. It contains the jobs that cannot be switched. Step 2. Calculate Ti , ∀i ∈ L. If Ti < 1, ∀i ∈ L, then stop; else, go to Step 3. Step 3. Select the first late job i ∈ L and i ∈ SJ. If none exists, then stop; else go to Step 4. Step 4. Check if Ci = d j for some late job j ∈ L. If so, then exchange jobs i and j; set L = L − { j}. Else, set SJ = SJ + {i}. Go to Step 3, in any case.

EQUAL PROCESSING TIME BICRITERIA SCHEDULING

235

Theorem 3. Algorithm A5 optimizes the NT/Total tardiness bicriteria function. Proof of Theorem 3: Let the schedule obtained by using Algorithm A5 be designated by S while the optimal schedule be designated by S
. To prove the optimality of S, we transform S
to S without worsening it. Consider the first two jobs of S
. Call these jobs i and j, and let job i follow job j. If di ≥ d j , then these jobs are already in EDD order. Otherwise, put job i in the EDD position. Note that, after arranging these two jobs in EDD, the total tardiness must remain identical to that in S
because, otherwise, S
must not be optimal. Now, if after putting job i in the EDD position, NT does not increase, the first two jobs of S
will now be in the EDD order like those in S without affecting NT and total tardiness, since EDD cannot worsen the total tardiness value. In case NT increases, then it must be that job i is late in S
and job j is early, and after arranging them in the EDD order both become late. This follows from the fact that if both jobs are early (late) in S
(while not in EDD order), then they remain early (late) after arranging them in EDD. Also, since d j > di (from above), if job j is late then so will be job i as job i follows job j by assumption. This situation is depicted in figure 4. Note that d j ≥ c
j and d j < c
j since job i remains late when arranged in EDD. Hence, ci
− di ≥ 1 in S
. In the EDD order, the completion time of job j is ci
and ci
− d j ≤ 1 (= 1 −  ≥ 0) since ci
= c
j + 1 and d j ≥ c
j . In the EDD order, the completion time of job i is c
j , and let c
j − di = δ (recall, job i is late in the EDD order). Therefore, total tardiness after arranging the jobs in EDD = 1 + δ − . In S
, the tardiness of job j = 0 (because it is early) and the tardiness of job i = ci
− di = c
j + 1 − di = 1 + δ, giving the total tardiness in S
= 1 + δ. Since, S
is optimal, it follows that  = 0 because, otherwise, S
can be improved by arranging the jobs in EDD. Therefore, ci
= d j + 1. Also, since ci
= c
j + 1, we have d j = c
j . Hence, the due date of job j must be the same as c
j . Consequently, we do not put job i in the EDD order if it makes S
worse. Instead, we fix job j at its current location. The above steps result in rearranging S
in such a way that either both the jobs are in EDD order or a job is fixed at its location in S
and the other job is in the EDD order (this aspect of the schedule is trivial for the first two jobs as we have only one job left after fixing the location of a job). But NT and total tardiness are not affected as putting the jobs in the EDD order does not worsen total tardiness and we ensure that NT does not increase by fixing the location of a job to that end. Next, we consider the first three jobs of S
, the first two of which have been rearranged as described above. Let this process has progressed to the first

Figure 4.

Jobs i and j in S
. Job i is late and job j is early, i.e., d j ≥ c
j order and, hence, di < d j .

236

SARIN AND PRAKASH

n jobs in S
in which some jobs are fixed at their positions while the remaining jobs are in the EDD order. Now, consider the n + 1st job of S
. If this job is not in the EDD order among those that are not fixed, then put it in the EDD position. If NT does not increase as a result, we once again have a set of fixed jobs (those obtained as a result of the rearrangement of the first n jobs of S
) and the others in the EDD order. If NT increases, we fix the positions of those jobs at their present locations that cause the worsening of NT and arrange the other jobs in EDD. Once again, we have a set of jobs that are fixed at their positions while the others are arranged in EDD; the total tardiness of the resultant schedule does not worsen and NT remains unchanged. The schedule S
is thus transformed to a schedule in which the jobs are in the EDD order except those that are fixed at their latest possible location without affecting NT and total tardiness. This schedule is identical to S. The following result follows from the above. Corollary. Given a set of jobs initially arranged in the EDD order and the primary criterion of minimizing total tardiness, we need to exchange a late job only with another late job or a job having the same due date in order to potentially improve the value of a secondary criterion. Weighted completion time/total tardiness Next, we present an algorithm, designated Algorithm A6, to obtain the optimal schedule for these criteria. Algorithm A6 (Optimization of weighted completion time given total tardiness) Step 1. Arrange all the jobs in the EDD order with the ties broken according to the WSPT rule. Assign the jobs in this order to the earliest available machine. Let SJ denote a set of jobs. Initially, SJ = ∅. Let L be the set of all late jobs in the current schedule. Step 2. Pick the first late job i ∈ SJ. If none exists, then go to Step 4; else, go to Step 3. Step 3. Check the late jobs after job i. If there exists a j ∈ L, j = i such that Ci ≥ d j and wi < w j , then exchange job i with that job j which has the maximum weight amongst all eligible jobs; update L, if necessary; else, set SJ = SJ + {i} and go to Step 2 anyway. Step 4. Pick the first job i that is not late and i ∈ SJ. If none exists, then stop; else, go to Step 5. Step 5. Check all other early jobs j after i in the schedule for Ci ≤ d j and C j ≤ di and wi < w j . If it is true, then exchange the job i with the eligible job j that has the maximum weight amongst all eligible jobs; else, set SJ = SJ + {i}. Go to Step 4 anyway. Theorem 4.

Algorithm A6 optimizes weighted completion time/total tardiness.

Proof of Theorem 4: Case 1.

The proof is divided into the following cases:

Jobs j and i ∈ L

EQUAL PROCESSING TIME BICRITERIA SCHEDULING

237

This case corresponds to Step 3 of the algorithm. It follows directly from Corollary 1. If the conditions Ci ≥ d j , wi > w j for i, j ∈ L, with j appearing after i in the schedule, are violated, then the primary criterion will be violated. Case 2.

Jobs j and i ∈ L

This corresponds to Step 5 of the algorithm. It follows from the fact that the early jobs, after being switched with each other, should remain early because, otherwise, the tardiness of the system will increase, thereby, violating the primary criterion. The conditions specified in Step 5 maintain feasibility. The algorithm scans through all the late jobs first since some of the late jobs may become early while switching. Then, it scans through all the early jobs. There are finite number of jobs that will satisfy the given condition, and that number will keep decreasing due to increment of set SJ. Hence, the algorithm will stop whenever no more switches are possible. Next, we consider the primary criterion of NT. T max or total tardiness/NT Algorithm A7 (Minimization of T max or total tardiness given NT) Step 1. Let L be the set of late jobs obtained by Algorithm A2. Arrange these jobs in EDD. Designate the remaining jobs as E. The jobs in set E are early. Step 2. Allocate the jobs in E, using Algorithm A1. Step 3. Let Fj be the set of the followers of a job j on all the machines, with job j being inclusive in set F j . Pick the first job i from the set L. If none exists, then stop; else, find the earliest job j in the schedule such that Ck
(the new completion time of job k after job i has been inserted in the current location of job j) ≤ dk , ∀k ∈ F j . If none exists, then go to Step 5; else, go to Step 4. Step 4. Insert job i in the current location of job j in the schedule. Set L = L − {i}; go to Step 3. If L is empty, then stop. Step 5. Assign the jobs, in set L, to the locations of the machines after those occupied by the jobs which have already been allocated, and stop. Theorem 5. Algorithm A7 optimizes: (a) Tmax/NT and, (b) Total Tardiness/NT. Proof of Theorem 5: Let the schedule obtained by using Algorithm A7 be designated by S while the optimal schedule be designated by S
. To prove the optimality of S, we transform S
to S without worsening it. Consider the first two jobs in S
. Call these jobs i and j with job i following job j. Arrange them in EDD if they are not in that order already. As noted earlier in the proof of

238

SARIN AND PRAKASH

Theorem 3, if the jobs are not in EDD and they are early (late), then they remain early (late) after arranging them in EDD as well. Also, if NT increases as a result of arranging them in EDD, then only one of these jobs must have been late in S
, and moreover, this must be job i because if job i is early in S
while being not in EDD, that is, di < d j , then job j must also be early, and if both the jobs are early in a non-EDD sequence, then NT cannot increase as a result of putting them in EDD order. In this case, we fix job j at its current location because by moving it we worsen NT. In case NT does not worsen as a result of putting the jobs in the EDD order from its value in S
, we keep them in EDD as putting the jobs early (or late) in the EDD order cannot worsen total tardiness and T max. Hence, since S
is optimal, the EDD order (if it does not worsen NT) moves the jobs as early as possible without affecting total tardiness and T max. The resulting schedule consists of jobs that are arranged in EDD except those that are fixed at the latest possible positions. Next, we consider the first three jobs in S
. Let this process has progressed to the nth step, that is, the first n jobs of S
have been rearranged as above. Consider the n + 1st job of S
and put this job in its EDD position among the jobs from the first n jobs of S
that are not fixed. If NT increases, we fix the jobs that worsen NT at their current locations. Otherwise, the jobs that are not fixed are in the EDD order. The resultant schedule is identical to S and consists of jobs in EDD except for those that are fixed at the latest possible position without violating the NT value of S
. z 2 /Weighted completion time From Remark 3, the weighted completion time is minimized by the WSPT order. Regarding the optimization of a secondary criterion for this case, it can easily be shown that no improvement is possible in a secondary criterion if the weights of all the jobs are distinct.

Table 1.

Summary of results for the unit processing time bicriteria problems. Secondary

Primary

Completion time

T max

Total tardiness

Number of tardy jobs

Weighted completion time

Completion time

–

EDD O(n log n) Algorithm A1

EDD O(n log n) Algorithm A1

Algorithm A2 O(n 2 log n)

WSPT O(n log n)

T max

EDD O(n log n) Algorithm A1

–

EDD O(n log n) Algorithm A1

Algorithm A3 O(n 2 log n)

Algorithm A4 O(n 2 log n)

Total tardiness

EDD O(n log n) Algorithm A1

EDD O(n log n) Algorithm A1

– O(n 2 log n)

Algorithm A5 O(n 2 log n)

Algorithm A6

Number of tardy jobs

Algorithm A2 O(n 2 log n)

Algorithm A7 O(n 2 log n)

Algorithm A7 O(n 2 log n)

–

Open

Weighted completion time

WSPT O(n log n)

Algorithm A8 O(n log n)

Algorithm A8 O(n log n)

Algorithm A8 O(n 2 log n)

–

EQUAL PROCESSING TIME BICRITERIA SCHEDULING

239

Hence, we can propose the following algorithm to optimize a secondary criterion/weighted completion time. Algorithm A8 (Minimization of secondary criterion given weighted completion time) Step 1. Arrange all the jobs in WSPT order. Step 2. Arrange all the jobs with the same weights using an algorithm that optimizes the given secondary criterion. Step 3. Assign the jobs one by one to the earliest available machine. A summary of the results obtained for the bicriteria problem is given in Table 1. The time complexities of the proposed algorithm are also indicated. All the proposed algorithms are of polynomial time complexity. The combination of primary and secondary criteria that is not analyzed is weighted completion time/NT. A polynomial time algorithm does not seem to exist for this case. 5.

Concluding remarks

In this paper, we have presented results for the equal processing time bicriteria scheduling problems on parallel machines. Various combinations of the primary and secondary criteria are considered, and algorithms are presented to schedule a given set of jobs on the machines. All the algorithms presented are of polynomial time complexity and are shown to generate optimal solutions. Notes 1. The justification behind this and subsequent Remarks is rather straightforward and is omitted here for the sake of brevity (see Prakash, 1998). 2. Since the processing times of all the jobs are the same, this can also be viewed as the Largest Weight First Rule.

References M. Azizoglu and S.O. Kondacki, “Bicriteria scheduling problem involving total tardiness and total earliness penalties,” International Journal of Production Economics, vol. 23, no. 1–3, 1991. R. Bausch, “Multicriteria scheduling tool using a branch and bound algorithm,” European Journal of Operational Research, vol. 61, no. 1/2, pp. 213–218, 1992. A.A. Cenna and M.T. Tabucanon, “Bicriteria scheduling problem in a job shop with parallel processors,” International Journal of Production Economics, vol. 25, no. 1-3, pp. 95–101, 1991. S. Chand and Schneeberger, “A note on single machine scheduling problem with minimum weighted completion time and maximum allowable tardiness,” Naval Research Logistics Quarterly, vol. 33, no. 3, pp. 551–557, 1986. C.L. Chen and R.L. Bulfin, “Scheduling unit processing time jobs on a single machine with multiple criteria,” Computers and Operations Research, vol. 17, pp. 1–17, 1989. C.-L. Chen, and R.L. Bulfin, “Complexity of single machine, multi-criteria scheduling problems,” European Journal of Operational Research, vol. 70, pp. 115–125, 1993.

240

SARIN AND PRAKASH

C.-L. Chen and R.L. Bulfin, “Scheduling a single machine to minimize two criteria: Max tardiness and number of tardy jobs,” IIE Transactions, vol. 26, pp. 76–84, 1994. T.C.E. Cheng, “Minimizing the flow time and missed due dates in a single machine sequencing,” Mathematical & Computer Modelling, vol. 13, no. 5, pp. 71–77, 1990. T.C.E. Cheng, “Improve solution procedure for n/1/max {γ (C)} → C scheduling problem,” Journal of Operations Research Society, vol. 42, no. 5, pp. 413–417, 1991. R.L. Daniels, “Incorporating preference information into multi-objective scheduling,” European Journal of Operational Research, vol. 77, pp. 272–286, 1994. P. De, J.B. Ghosh, and C.E. Wells, “Some clarifications on the bicriteria scheduling of unit execution time jobs on a single machine,” Computer and Operations Research, vol. 18, no. 8, pp. 717–720, 1991. P. Dileepan and T. Sen, “Bicriteria job shop scheduling with flowtime and sum square of lateness,” Engineering Cost and Production Economics, vol. 21, no. 3, pp. 295–299, 1991. T.D. Fry, R.D. Armstrong, and H. Lemis, “A framework for single machine multiple objective sequencing research,” Omega, vol. 17, pp. 595–607, 1989. B. Grabot and L. Geneste, “Dispatching rules in scheduling: A fuzzy approach,” International Journal of Production Research, vol. 32, no. 4, pp. 903–915, 1994. T.J. Hodgson and G.W. McDonald, “Interactive scheduling of a generalized flow shop, Part I: Success through evolutionary development,” Interfaces, vol. 11, no. 2, pp. 42–47, 1981. J.A. Hoogeveen, “Minimizing maximum promptness and maximum lateness on a single machine,” Mathematics of Operations Research, vol. 21, pp. 100–114, 1996a. J.A. Hoogeveen, “Single machine scheduling to minimize a function of two or three maximum cost criteria,” Journal of Algorithms, vol. 21, pp. 415–435, 1996b. J.A. Hoogeveen and S.L. van de Velde, “Minimizing total completion time and maximum cost simultaneously,” Operations Research Letters, vol. 17, pp. 205–208, 1995. K.S. Lin, “Hybrid algorithm for sequencing with bicriteria,” Journal of Optimization Theory and Applications, vol. 39, pp. 105–124, 1983. R.T. Nelson, R.K. Sarin, and R.L. Daniels, “Scheduling with multiple performance measures: The one-machine case,” Management Science, vol. 32, pp. 464–479, 1986. J.B. Pickens and J.G. Hoff, “Fuzzy goal programming in forestry, an application with special solution,” Fuzzy Sets and Systems, vol. 39, no. 3, pp. 239–246, 1991. C.N. Potts and K.R. Baker, “Flow shop scheduling with lot streaming,” Operations Research Letters, vol. 8, no. 6, pp. 297–303, 1989. D. Prakash, “Unit processing time bicriteria scheduling on parallel machines,” M.S. Thesis, Virginia Polytechnic Institute and State University, Blacksburg, Virginia, 1998. R. Ramesh and J.M. Cary, “Multicriteria job shop scheduling,” Computers and Industrial Engineering, vol. 17, pp. 597–602, 1989. S.C. Sarin and R. Hariharan, “A two machine bicriteria scheduling problem,” International Journal of Production Economics, vol. 65, no, 2, pp. 125–139, 2000. T. Sen, F.M.E. Raizhel, and P. Dilelepan, “Branch and bound approach to the bicriteria scheduling problem involving total flow time and range of lateness,” Management Science, vol. 23, pp. 1016–1019, 1977. W.E. Smith, “Various optimizers for single stage production,” Naval Research Logistics Quarterly, vol. 3, no. 1, March 1956. V. T
kindt and J.-C. Billaut, Multicriteria Scheduling: Theory, Models and Algorithms, Springer-Verlag: Berlin, 2002. G.L. Vairaktararis and C.-Y. Lee, “The single-machine scheduling problem to minimize total tardiness subject to minimum number of tardy jobs,” IIE Transactions, vol. 27, no. 2, pp. 250–256, 1995. V.L.N. van Wassenhove and L.F. Gelders, “Solving bicriterion scheduling problem,” European Journal of Operations Research, vol. 4, pp. 42–48, 1980. R.G. Vickson and B.E. Alfredson, “Two and three machine flow shop scheduling porblems with equal sized transfer batches,” International Journal of Production Research, vol. 30, pp. 1551–1574, 1992. R.J. Wittrock, “Scheduling algorithms for flexible flow lines,” IBM Journal of Research and Development, vol. 29, pp. 401–412, 1985.