Parallel machine scheduling about an unrestricted due date and additional resource constraints.

JOSE A. VENTURA [1]

DAECHEOL KIM [2]

This research considers the problem of scheduling jobs on parallel machines with an unrestricted due date and additional resources. The objective is to minimize the total absolute deviation of job completion times about the common due date.

This problem is motivated by restrictions that occur in the handling and processing of jobs in certain phases of semiconductor manufacturing and other production systems. It is shown that the problem is polynomial when there exists one single type of additional resource and the resource requirements per job are zero or one.

1. Introduction

The study of parallel machine scheduling with additional resource constraints is a new area of research. In most of the classical parallel machine scheduling problems only machines are constrained resources [1]. Thus, at any time, the execution of a job is restricted by the availability of a single scarce resource. However, in some manufacturing systems, jobs may also require, besides machines, certain additional limited resources for their handling and processing, such as automated guided vehicles, machine operators, tools, pallets, fixtures, industrial robots, etc. A practical example of such a scheduling problem can be found in the burn-in operation in the final testing stage of semiconductor manufacturing. In the burn-in operation, very large integrated circuits undergo thermal stress in an oven for a certain period of time at a constant temperature in order to anneal out latent defects. After the batch of circuits arrives at the burn-in area, they are loaded onto boards, and thus the absence of the neces sary boards prevents the batch from being loaded into the oven. In practice this corresponds to assigning the available boards to the batches awaiting burn-in off-line and treating each batch as an individual job. Thus, boards are considered as additional limited resources. Once the boards are loaded into the oven, no board can be removed from the oven until the processing of the job is completed [2,3].

A few scheduling models have appeared in the literature which explicitly take additional limited resources into consideration (see, for example, Blazewicz [4]). Garey and Johnson [5] examine the computational complexity of multiprocessor scheduling problems, where the scheduling length is the criterion. In Blazewicz et al. [6], models involving parallel machines, unit processing time jobs and the maximum lateness criterion are studied in detail. Blazewicz et al. [7] consider the scheduling of independent jobs on an arbitrary number of identical parallel processors in order to minimize mean flow time with one additional resource type and 0-1 resource requirements. They prove that an optimal schedule exists such that all jobs requiring a unit of additional resource available in b units can be assigned to the first b machines.

Most previous parallel machine scheduling research with additional resources has dealt with performance criteria such as makespan, mean tardiness, mean lateness, etc. With the increasing interest in Just-In-Time (JIT) production, the classical measures of performance are no longer applicable. Instead, the emphasis has shifted towards earliness and tardiness (E-T) scheduling taking earliness as well as tardiness into consideration. In a JIT production environment, not only lost sales and goodwill associated with tardiness are recognized, but also the awareness in the costs associated with early job completion is heightened, which include the opportunity cost of tied-up capital, increased floor space requirement, extra insurance, and loss due to deterioration.

There are a number of different ways to represent the JIT concept in scheduling models, with an important special case in the family of E-T problems being the minimization of the sum of absolute deviations of job completion times from a common due date [8]. Scheduling problems with a common due date is relevant to certain manufacturing applications. Kanet [9] has mentioned the example of a job shop which produces components for subsequent assembly into finished products. The production of perishable goods is yet another example where earliness and tardiness penalties with respect to a common due date are realistic. Suppose, for example, a chemical manufacturer combines chemicals X and Y, which deteriorate rapidly, to produce chemical Z. If chemicals X and Y are produced before their common due date, they may deteriorate. If one or both of them are produced late, one may deteriorate and delays in the production of Z may prove costly. In this paper, we address the problem of minimizing the Total Absolute Devia tion (TAD) of job completion times about a common due date with an arbitrary number of identical parallel machines, one additional resource type and 0-1 resource requirements.

The rest of the paper is organized as follows. An integer linear programming (ILP) formulation is provided in the next section. In Section 3, several dominance properties are established. In addition, it is shown that the optimality property proved by Blazewicz et al. [7] is also applicable to our problem. In Section 4, by utilizing these dominance properties, the problem is reformulated as an assignment problem which can be solved in polynomial time. In the last section, the value of the work is summarized and future developments are proposed.

2. Zero-one ILP formulation

We are given a set of n jobs J = {1,2,...,n} to be processed on a set of m identical parallel machines P = {[P.sub.1], [P.sub.2],...,[P.sub.m]} with one additional resource type available in b units (b [less than] m). Each job requires for its processing an arbitrary machine and at most one unit of additional resource. All jobs are assumed to be non-preemptable and available at time zero. Let R(j) represent the amount of additional resource required by job j, where R(j) [epsilon] {0, 1}, [P.sub.j] the processing time of job j, and d the unrestricted due date common for all jobs. It is assumed here that all required resources are allocated to a job when its processing begins, and they are returned by the job right after its completion. Resources are referred to as being renewable under this assumption. Without loss of generality we assume that all [p.sub.j], d, and b are positive integers.

For a given schedule, let [s.sub.j] denote the start time of job j, and [c.sub.j] the completion time of job j, i.e., [c.sub.j] = [s.sub.j] + [p.sub.j]. We will use the TAD criterion which is defined as TAD = [[[sigma].sup.n].sub.j=1][max{0,[c.sub.j] - d} + max{0, d - [c.sub.j]}]. In the notation of Blazewicz et al. [10], the problem can be denoted by P\res 1.l, [p.sub.j], [d.sub.j] = d\ TAD.

Let [C.sub.jt] be the cost of job j when its processing is completed at time t. Thus, [C.sub.jt] can be expressed as follows:

[C.sub.jt] = {(d - t) if d [greater than or equal to] t, (t - d) if d [less than] t.

Let [t.sub.1] and [t.sub.h] be lower and upper bounds to the start and completion times of any optimal schedule, respectively. Obviously, 0 [less than or equal to] [t.sub.1] [less than] [t.sub.h]. Then, the 0-1 ILP formulation for the problem can be expressed as:

min [[[sigma].sup.n].sub.j=1] [[[sigma].sup.[t.sub.h].sub.t=[t.sub.1]+[p.sub.j]] [C.sub.jt] [Y.sub.jt], (1)

subject to

[[[sigma].sup.n].sub.j=1][X.sub.jt] [less than or equal to] m, t = [t.sub.1] + 1,...,[t.sub.h], (2)

[[[sigma].sup.n].sub.j=1] R(j)[x.sub.jt] [less than or equal to] b, t = [t.sub.1] + 1,...,[t.sub.h], (3)

[[[sigma].sup.[t.sub.h].sub.t=[t.sub.1]+1] [X.sub.jt] = [P.sub.j], j = 1,...,n, (4)

[P.sub.j][Y.sub.jt] [less than or equal to] [[[sigma].sup.t].sub.k=t-[P.sub.j]+1] [X.sub.jk], j = 1,...,n; t = [t.sub.1] + [P.sub.j],...,[t.sub.h], (5)

[[[sigma].sup.[t.sub.h].sub.t=[t.sub.1]+[P.sub.j]] [Y.sub.jt] = 1, j = 1,2,...,n, (6)

[x.sub.jt] [epsilon] {0,1}, j = 1,...,n; t = [t.sub.1] + 1,...,[t.sub.h], (7)

[y.sub.jt] [epsilon] {0,1}, j = 1,...,n; t = [t.sub.1] + [P.sub.j],...,[t.sub.h], (8)

where

[y.sub.jt] = {1 if job j is completed at time t, 0 otherwise,

[X.sub.jt] = {1 if job j is being processed on the time interval (t - 1, t), 0 otherwise.

Constraint (2) ensures that no more than m jobs are assigned to any time unit. Constraint (3) guarantees that additional resources assigned at each time unit are within their limit. Constraints (4) and (5) ensure that each job is continuously processed to its completion. Constraints (6) ensure that each job is assigned to a machine only one time. The above 0-1 ILP formulation precisely models the problem, but it does not take advantage of the fact that there is a common due date. This formulation can also be utilized when due dates are job dependent. In this case, the cost coefficients for each job have to be defined with respect to the corresponding due date.

Dominance properties for the case of an unrestricted common due date are provided in the next section. These properties show that there always exist an optimal schedule in which all jobs requiring one unit of additional resource are assigned only to the first b machines. Based on this result, it is shown in Section 4 that the problem can be formulated as an asymmetric assignment problem without considering the resource constraints explicitly.

3. Dominance properties

In this section, four lemmas and three theorems are proved. Specifically, Lemmas 1 and 2, and Theorem 1 imply that an optimal schedule exists such that all jobs in set [J.sub.r] [intersection] (E [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Q) can be processed only on the first b machines, where [J.sub.r] = {j [epsilon] J : R(j) = l}, E = {j [epsilon] J: [c.sub.j] [less than or equal to] d}, and Q = {j [epsilon] J: [s.sub.j] [less than] d [less than] [c.sub.j]}. Similarly, Lemmas 3 and 4, and Theorem 2 show the same property for all jobs in set [J.sub.r] [intersection] (T [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Q), where T = {j [epsilon] J: [s.sub.j] [greater than or equal to] d}. Finally, Theorem 3 proves the property for all jobs in set [J.sub.r]. Let [M.sub.k] = {j [epsilon] J: job j is assigned to machine [P.sub.k]}, [M.sub.R] = {j [epsilon] J: job j is assigned to machine [P.sub.k], k = 1,...,b}, [M.sub.H] = {j [epsilon] J: job j is assigned to machine [P.sub.k], k = b + 1,...,m}, R = {l,2,...,b}, H = {b + 1,...,m}, [J.sub.0] = J - [J.sub.r], and [[alpha].sub.k] = max {0, [max.sub.j[epsilon][J.sub.r][intersection](E[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]Q)[intersection][M.sub. k]]{c.sub.i]}}.

Lemma 1. For problem P\res 1.1, [p.sub.j], [d.sub.j] = d\TAD, a new schedule which satisfies the following condition can always be constructed from any feasible schedule with the same objective value:

[[alpha].sub.k], [greater than or equal to] [[alpha].sub.h], for k [epsilon] R and h [epsilon] H. (9)

Proof. Let [sigma] be a feasible schedule which does not satisfy condition (9). Therefore, there exist a pair of machines [P.sub.i] and [P.sub.j], i [epsilon] R and j [epsilon] H, such that [[alpha].sub.i] [less than] [[alpha].sub.j]. In this case, all the jobs in machine [P.sub.i] are reassigned to machine [P.sub.j] and all the jobs in machine [P.sub.j] are reassigned to machine [P.sub.i] maintaining the same starting and completion times for all jobs. Proceed with this exchange of jobs among machines until condition (9) is satisfied. Since there is a finite number of machines, a finite number of exchanges is required. Let [sigma]' be the resulting schedule. Let z([sigma]) and z([sigma]') be the objective function values of [sigma] and [sigma]', respectively. Note that z([sigma]) = z([sigma]') since job completion times did not change. This completes the proof.

Lemma 2. For problem P\res 1.1, [p.sub.j], [d.sub.j] = d\ TAD, if there exists a job y such that [c.sub.y] = [max.sub.j[epsilon][J.sub.r][intersection](E[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]Q)[intersection][M.sub. H]] {[c.sub.j]} in a feasible schedule [sigma] which satisfies condition (9), then [W.sub.1] = [Empty Set], where [W.sub.1] = {j [epsilon] [J.sub.0] [intersection] Q [intersection] [M.sub.R] : [s.sub.j] [less than] [c.sub.y] [less than or equal to] [c.sub.j] in [sigma]}.

Proof. Let [sigma] be a feasible schedule that satisfies condition (9) and has a job y such that [c.sub.y] = [max.sub.j[epsilon][J.sub.r][intersection](E[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]Q)[intersection][M.sub. H]] {[c.sub.j]}. Condition (9) implies that all jobs in set [J.sub.r] [intersection] Q are in [M.sub.R]. Consider the following two cases:

(i) If \[J.sub.r] [intersection] Q\ = b, then [J.sub.0] [intersection] Q [intersection] [M.sub.R] = [Empty Set]. Thus, [W.sub.1] = [Empty Set].

(ii) If \[J.sub.r] [intersection] Q\ [less than] b, it may be true that there exists a job j such that j [epsilon] [J.sub.0] [intersection] Q [intersection] [M.sub.R]. In this case, let j be a job in [M.sub.k], k [epsilon] R. Then, it is obvious that [[alpha].sub.k] [less than or equal to] [s.sub.j]. In addition, by condition (9), [c.sub.y] [less than or equal to] [[alpha].sub.i], for all i [epsilon] R. Therefore, [c.sub.y] [less than or equal to] [s.sub.j] and [W.sub.1] = [Empty Set]. This completes the proof.

Theorem 1. For problem P\res 1.1, [p.sub.j], [d.sub.j] = d\ TAD, there always exists an optimal schedule such that all jobs in set [J.sub.r] [intersection] (E [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Q) are assigned only to machines [P.sub.1], [P.sub.2],...,[P.sub.b].

Proof. Let [[sigma].sup.*] be an optimal schedule which satisfies condition (9) but not all jobs in set [J.sub.r] [intersection] (E [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Q) are assigned only to the first b machines. Then, by Lemma 2, [J.sub.r] [intersection] E [intersection] [M.sub.H] [not equal to] [Empty Set] in [[sigma].sup.*]. Let y be a job such that [c.sub.y] = [max.sub.j[epsilon][J.sub.r][intersection]E[intersection][M.sub.H]] {[c.sub.j]}. Note that, if there exists a job j [epsilon] E [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Q assigned to [P.sub.k], k [epsilon] R, such that [s.sub.j] [less than] [c.sub.y] [less than or equal to] [c.sub.j], then j [epsilon] [J.sub.0] [intersection] E since [W.sub.1] = [Empty Set] by Lemma 2.

Consider a new schedule [sigma] with objective function value z([sigma]) = z([[sigma].sup.*]) in which the jobs from set [J.sub.r] [intersection] (E [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Q) are all assigned to machines [P.sub.1], [P.sub.2],...,[P.sub.b], but some jobs in set [J.sub.0] [intersection] E may have to be split into two sub-jobs. The new schedule [sigma] can be obtained from schedule [[sigma].sup.*] in the following way:

(i) In schedule [[sigma].sup.*], there exists no job i [epsilon] E [intersection] [M.sub.k], k [epsilon] R, such that [s.sub.i] [less than] [c.sub.y] [less than] [c.sub.i]. In this case, all jobs in set {j [epsilon] E: [c.sub.j] [less than or equal to] [c.sub.y] and j [epsilon] [M.sub.h], h [epsilon] H, in [[sigma].sup.*]} are reassigned to machine [P.sub.k] and those jobs from set {i [epsilon] E : [c.sub.i] [less than or equal to] [c.sub.y] and j [epsilon] [M.sub.k], k [epsilon] R in [[sigma].sup.*]} are reassigned to machine [P.sub.h] maintaining the same starting and completion times for all jobs.

(ii) In schedule [[sigma].sup.*], there exists a job j [epsilon] [J.sub.0] [intersection] E [intersection] [M.sub.k], k [epsilon] R, such that [s.sub.j] [less than] [c.sub.y] [less than] [c.sub.j]. Now j is partitioned into two sub-jobs, [j.sub.1] and [j.sub.2]: [j.sub.1] with starting time [s.sub.[j.sub.1]] = [c.sub.y] and completion time [c.sub.[j.sub.1]] = [c.sub.j], and [j.sub.2] with starting time [s.sub.[j.sub.2]] = [s.sub.j] and completion time [c.sub.[j.sub.2]] = [c.sub.y]. Then, the reassignment of jobs to machines [P.sub.k] and [P.sub.h] is performed in the same way as described in case (i).

Note that the reassignment of jobs in machines [P.sub.k] and [P.sub.h] does not violate the resource constraints, and does not change job starting and completion times. By proceeding in this way, for each job j [epsilon] [J.sub.r] [intersection] E [intersection] [M.sub.H], we obtain a new schedule [sigma] such that:

(a) all jobs from set [J.sub.r] [intersection] (E [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Q) are assigned to machines [P.sub.1], [P.sub.2],...,[P.sub.b] and the resource constraints are satisfied;

(b) all jobs that are partitioned belong to [J.sub.0] [intersection] E. If job j is partitioned into two sub-jobs [j.sub.1] and [j.sub.2], then [j.sub.1] [epsilon] [M.sub.R], and [j.sub.2] [epsilon] [M.sub.H];

(c) starting and completion times of all jobs in schedules [sigma] and [[sigma].sup.*] are the same; and

(d) z([sigma]) = z([[sigma].sup.*]).

Now, it is shown how to remove partitioned jobs in schedule [sigma]. Let [J.sub.s] = {j [epsilon] [J.sub.0] [intersection] E: j is split into two sub-jobs in [sigma]}. Let [j.sub.1] and [j.sub.2] be the sub-jobs of job j [epsilon] [J.sub.s], such that [c.sub.[j.sub.2]] = [min.sub.i[epsilon][J.sub.s]] {[c.sub.[i.sub.2]]}. Note that [j.sub.1] [epsilon] [M.sub.k], k [epsilon] R, and [j.sub.2] [epsilon] [M.sub.h], h [epsilon] H. Then, let [A.sub.E] = {i [epsilon] E : [s.sub.i] [less than] [s.sub.[j.sub.1]] and i [epsilon] [M.sub.k] in [sigma]}, [B.sub.E] = {i [epsilon] E : [s.sub.i] [less than] [s.sub.[j.sub.2]] and i [epsilon] [M.sub.h] in [sigma]}, [a.sub.E] = \[A.sub.E]\, and [b.sub.E] = \[B.sub.E]\.

Consider a new schedule [sigma]' which can be constructed by removing all partitioned jobs in schedule [sigma]. The following procedure removes the partition of job j depending on the relation between [a.sub.E] and [b.sub.E]. Two cases are considered:

(i) [a.sub.E] [greater than] [b.sub.E]: subjob [j.sub.1] is removed from [P.sub.k], k [epsilon] R, and the whole job j is assigned to [P.sub.h], h [epsilon] H, with new start time [s'.sub.j] = [s.sub.j] - [p.sub.[j.sub.1]]. Then each job in set [A.sub.E] is shifted by [p.sub.[j.sub.1]], time units to the right and each job in set [b.sub.E] is shifted by [p.sub.[j.sub.1]] time units to the left with respect to [sigma]. Thus, z([sigma]') increases by ([b.sub.E] + l) [p.sub.[j.sub.1]] with respect to z([sigma]) and, at the same time, decreases by [a.sub.E][p.sub.[j.sub.i]]. Therefore, z([sigma]') - z([sigma]) [less than or equal to] 0.

(ii) [a.sub.E] [less than or equal to] [b.sub.E]: subjob [j.sub.2] is removed from [P.sub.h], h [epsilon] H, and the whole job j is assigned to [P.sub.k], k [epsilon] R, with new start time [s'.sub.j] = [s.sub.j]. Then each job in set [A.sub.E] is rescheduled [p.sub.[j.sub.2]] time units earlier and each job in [B.sub.E] is rescheduled [p.sub.[j.sub.2]] time units later than in [sigma]. Thus, z([sigma]') decreases by [b.sub.E][p.sub.[j.sub.2]] with respect to z([sigma]) and, at the same time, increases by [a.sub.E][p.sub.[j.sub.2]]. Therefore, z([sigma]') - z([sigma]) [less than or equal to] 0.

It is easy to see that proceeding with the above procedure until there is no partitioned job results in a feasible schedule [sigma]' which satisfies condition (a). Since z([sigma]') [less than or equal to] z([sigma]) = z([[sigma].sup.*]), there exists an optimal schedule such that all jobs from set [J.sub.r] [intersection] (E [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Q) are assigned only to machines [P.sub.1], [P.sub.2],...,[P.sub.b].

Lemma 3. For problem P\res 1.1, [p.sub.j], [d.sub.j] = d\ TAD, a new schedule which satisfies the following condition can always be constructed from any feasible schedule with the same objective value:

[[beta].sub.k] [less than or equal to] [[beta].sub.h], for k [epsilon] R and h [epsilon] H, (10)

where [[beta].sub.k] = max{0, [min.sub.j[epsilon][J.sub.r][intersection]T[intersection]Q[intersecti on][M.sub.k]] {[s.sub.i]}}.

Proof Let [sigma] be a feasible schedule that does not satisfy condition (10). Therefore, there exist some machines [P.sub.i], and [P.sub.j], i [epsilon] R and j [epsilon] H, such that [[beta].sub.i] [greater than] [[beta].sub.j]. In this case, all the jobs in machine [P.sub.i], are reassigned to machine [P.sub.j] and all the jobs in machine [P.sub.j] are reassigned to machine [P.sub.i], maintaining the same starting and completion times for all jobs. Proceed with this exchange of jobs among machines until condition (10) is satisfied. Since there is a finite number of machines, a finite number of exchanges is required. Let [sigma]' be the resulting schedule. Let z([sigma]) and z([sigma]') be the objective function values of [sigma] and [sigma]', respectively. Note that z([sigma]) = z([sigma]') since job completion times did not change. This completes the proof.

Lemma 4. For problem P\res 1.1,[p.sub.j], [d.sub.j] = d\ TAD, if there exists a job y such that [s.sub.y] = [max.sub.j[epsilon][J.sub.r][intersection](T[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]Q)[intersection][M.sub. H]] {[s.sub.j]} in a feasible schedule [sigma] which satisfies condition (10), then [W.sub.2] = [Empty Set], where [W.sub.2] = {j [epsilon] [J.sub.0] [intersection] Q [intersection] [M.sub.R] : [s.sub.j] [less than or equal to] [s.sub.y] [less than] [c.sub.j] in [sigma]}.

Proof. Let [sigma] be a feasible schedule that satisfies condition (10) and has a job y such that [s.sub.y] = [max.sub.j[epsilon][J.sub.r][intersection](T[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]Q)[intersection][M.sub. H]] {[s.sub.j]}. Condition (10) implies that all jobs in set [J.sub.r] [intersection] Q are in [M.sub.R]. Consider the following two cases:

(i) If \[J.sub.r] [intersection] Q\ = b, then [J.sub.0] [intersection] Q [intersection] [M.sub.R] = [Empty Set]. Thus, [W.sub.2] = [Empty Set].

(ii) If \[J.sub.r] [intersection] Q\ [less than] b, it may be true that there exists a job j such that j [epsilon] [J.sub.0] [intersection] Q [intersection] [M.sub.R]. In this case, let j be a job in [M.sub.k], k [epsilon] R. It is obvious that [[beta].sub.k] [greater than or equal to] [c.sub.j]. In addition, by condition (10), [s.sub.y] [greater than or equal to] [[beta].sub.i], for all i [epsilon] R. Therefore, [c.sub.j] [less than or equal to] [s.sub.y] and [W.sub.2] = [Empty Set]. This completes the proof.

Theorem 2. For problem P\res 1.1, [p.sub.j], [d.sub.j] = d\ TAD, there always exists an optimal schedule such that all jobs in set [J.sub.r] [intersection] (T [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Q) are assigned only to machines [P.sub.1], [P.sub.2],...,[P.sub.b].

Proof. The proof is similar to that of Theorem 1.

Theorem 3. For problem P\res 1.1, [p.sub.j], [d.sub.j] = d\ TAD, there always exists an optimal schedule such that all the jobs in set [J.sub.r] are assigned only to the first b machines

Proof. Let [[sigma].sup.*] be an optimal schedule such that not all jobs in set [J.sub.r] are assigned to the first b machines. By Theorems 1 and 2, a new schedule [sigma] can be constructed such that all jobs in each set [J.sub.r] [intersection] (E [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Q) and [J.sub.r] [intersection] (T [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Q) are assigned to only b machines with z([sigma]) [less than or equal to] z([[sigma].sup.*]). However, it may be possible that [P.sub.E] [not equal to] [P.sub.T] in schedule [sigma] even if \[P.sub.E]\ = \[P.sub.T]\ = b, where [P.sub.E] = {[P.sub.i] [epsilon] P: job j [epsilon] [J.sub.r] [intersection] (E [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Q) is processed in [P.sub.i] = 1,...,m} and [P.sub.T] = {[P.sub.i] [epsilon] P: job j [epsilon] [J.sub.r] [intersection] (T [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Q) is processed in [P.sub.i], i = 1,... ,m}.

If [P.sub.E] [not equal to] [P.sub.T] in schedule [sigma], then we need to show that a new schedule can be constructed such that [P.sub.E] = [P.sub.T] and the objective function value of the new schedule is no worse than that of [sigma]. First, a new schedule [sigma]' with Q = [Empty Set] is constructed from the original schedule [sigma]. Let j be a job such that j [epsilon] Q [intersection] [M.sub.k] in [sigma]. Note that shifting the schedule on machine [P.sub.k] to the right or to the left by d - [s.sub.j] or [c.sub.j] - d, respectively, does not violate the resource constraints in [sigma]. By Kanet [9], it is no worse to make job j start or complete exactly at the due date d. Therefore, repeating this until Q = [Empty Set] for all machines results in a new schedule [sigma]' with z([sigma]') [less than or equal to] z([sigma]). This requires a finite number of shifts.

Finally, a new schedule [sigma]" with [P.sub.E] = [P.sub.T] and z([sigma]") = z([sigma]') can be constructed from [sigma]'. Since Q = [Empty Set] and \[P.sub.E]\ = \[P.sub.T]\ = b in [sigma]', all jobs in set {j [epsilon] E : [s.sub.j] [less than or equal to] d and j [epsilon] [M.sub.h], where [P.sub.h] [epsilon] [P.sub.E] and h [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] R in [sigma]'} can be reassigned to [P.sub.k] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [P.sub.E], k [epsilon] R, and at the same time, all jobs in set {j [epsilon] E : [s.sub.j] [less than or equal to] d and j [epsilon] [M.sub.k], where [P.sub.k] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [P.sub.E] and k [epsilon] R in [sigma]'} are reassigned to [P.sub.h] maintaining the same starting and completion times for all jobs. Similarly, all jobs in set {j [epsilon] T : d [less or equal to] [s.sub.j] and j [epsilon] [M.sub.h], where [P.sub.h] [epsilon] [P.sub.T] and h [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] R in [sigma]'} can be reassigned to [P.sub.k] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [P.sub.T], k [epsilon] R, and at the same time, all jobs in set {j [epsilon] T : d [less or equal to] [s.sub.j] and j [epsilon] [M.sub.k], where [P.sub.k] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [P.sub.T] and k [epsilon] R in [sigma]'} are reassigned to [P.sub.h]. Repeating this until [J.sub.r] [intersection] [M.sub.h] = [Empty Set] for all h [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] R results in a new schedule. Let this new schedule be [sigma]" with objective function value z([sigma]"). Then, in schedule [sigma]", only the first b machines have the jobs in set [J.sub.r], and z([sigma]") = z([sigma]"). Since z([sigma]") = z([sigma]') [less or equal to] z([sigma]) = z([[sigma].sup.*]), there exists an optimal schedule such that all jobs in set [J.sub.r] are assigned only to machines [P.sub.1], [P.sub.2], ... , [P.sub.b]. This completes the proof.

The objective function of schedule [sigma]" can be expressed as follows:

Z([sigma]") = [[[sigma].sup.m].sub.i=1] ([[[sigma].sup.[e.sub.i]].sub.k=1] [E.sub.[i,k]] + [[[sigma].sup.[t.sub.i]].sub.k=1] [T.sub.[i,k]]), (11)

where, for each machine [P.sub.i] [epsilon] P in [sigma]", [E.sub.[i,k]] and [T.sub.[i,k]] are the earliness and tardiness panalties of the kth job from the beginning and from the end of the schedule, respectively, and [e.sub.i] and [t.sub.i] are the number of jobs in sets E and T in [P.sub.i], respectively. Since there is no straddling job in schedule [sigma]", the penalties are defined by sums of [P.sub.i]'s. A more detailed description for the first and second terms of (11) is as follows (see also Fig. 1):

[E.sub.[i,1]]: pE,2 + pE,3 + ... + pE,k + ... + pE,[e.sub.i],

[E.sub.[i,2]]: pE,3 + ... + pE,k + ... + pE,[e.sub.i],

... ...

[E.sub.[i,k]]: pE,k+1 + ... + pE,[e.sub.i],

... ...

[E.sub.[i,[e.sub.i]]]: 0.

Therefore,

[[[sigma].sup.[e.sub.i]].sub.k=1] [E.sub.[i,k]] = 1pE,2 + 2pE,3 + ... + (k - 1)pE,k

+ ... + ([e.sub.i] - 1)pE,[e.sub.i]. (12)

Similarly,

[T.sub.[i,1]] : pT,1 + pT,2 + pT,3 + ... + pT,k + ... + pT,[t.sub.i],

[T.sub.[i,2]]: pT,2 + pT,3 + ... pT,k + ... + pT,[t.sub.i],

... ...

[T.sub.[i,k]]: pT,k + ... + pT,[t.sub.i],

... ...

[T.sub.[i,[t.sub.i]]]: pT,[t.sub.i].

Therefore,

[[[sigma].sup.[t.sub.i]].sub.k=1] [T.sub.[i,k]] = 1pT,1 + 2pT,2 + 3pT,3 + ... + kpT,k + ... + [t.sub.i]pT,[t.sub.i], (13)

where jobs (E,k) and (T,k) are the kth jobs from the beginning and from the end of schedule [sigma]" on machine [P.sub.i].

4. Reformulation as an assignment problem

By Theorem 3, there exits an optimal schedule for problem P\res 1.1, [p.sub.j],[d.sub.j] = d\ TAD such that any change of jobs requiring an additional resource on the first b machines does not violate the resource constraints, and the property that one job completes exactly at the due date for each machine is satisfied. In this optimal schedule, all jobs in set [J.sub.r] are assigned only to machines [P.sub.1], [P.sub.2],...,[P.sub.b]. By these properties, the problem can be reduced to an asymmetric assignment problem. Let [C.sub.ijkl] be the cost of assigning joh j to the kth position from the beginning (if l = 1) or from the end (if l = 2) of the schedule for machine [P.sub.i]. If job j is in the kth position of the schedule for machine [P.sub.i], then, by Eduation (12), the total cost caused by this job is (k - 1) [p.sub.j]. If job j is in the kth position from the end of the schedule for machine [P.sub.i], then, by Eduation (13), the total cost generated by this job is [kp.sub.j]. Note that any job j [epsilon] J - [J.sub.r] can be assigned to any machine, but any job j [epsilon] [J.sub.r] can be assigned only to the first b machines. A more detailed expression of [C.sub.ijkl] is as follows:

[C.sub.ijkl] = {(k - 1) [p.sub.j], if i = 1,...,b; j = 1,...,n; k = 1,...n; l =1 or if i = b + 1,...,m; j = 1,...,n; R(j) = 0; k = 1,...,n; l = 1, [kp.sub.j], if i = 1,...,b; j = 1,...,n; k = 1,...,n; l = 2 or if i = b + 1,...,m; j = 1,...,n; R(j) = 0; k = 1,...,n; l = 2, [infinity], otherwise.

Then, the transportation network consists of n senders (j), representing jobs, and mnl receivers (i,k,l), representing machines, job positions, can earliness or tardiness penalties. In this formulation [C.sub.ijkl] is the unit cost and [x.sub.ijkl] is the decision variable representing the flow, both associated with are (j,(i,k,l)). The problem of finding a schedule with minimum TAD cost is equivalent to solving the following asymmetric assignment problem:

Min [[[sigma].sup.m].sub.i=1] [[[sigma].sup.n].sub.j=1] [[[sigma].sup.n].sub.k=1] [[[sigma].sup.2].sub.l=1] [C.sub.ijkl][x.sub.ijkl], (14)

subject to

[[[sigma].sup.m].sub.i=1] [[[sigma].sup.n].sub.k=1] [[[sigma].sup.2].sub.l=1] [x.sub.ijkl] = 1, j = 1, ....n, (15)

[[[sigma].sup.n].sub.j=1] [x.sub.ijkl] [less than or equal to] 1, i = 1,....,m; k = 1,....,n; l = 1, 2, (16)

[x.sub.ijkl] [greater than or equal to] 0, i = 1, ...,m; j = 1,...,n; k = 1,...,n; l = 2,2, (17)

where

[x.sub.ijkl] = { 1 if job j is processed on machine [P.sub.i] in the kth position from the beginning (l = 1) or from the end (l = 2) of the schedule, 0 otherwise.

It follows that an optimal schedule can be obtained by an assignment algorithm (e.g., the auction algorithm of Bertsekas [11] and the Hungarian algorithm of Kuhn [12]). An example of this problem with five independent jobs and two identical parallel machines is provided. Processing times and resource requirements for the jobs are presented in Table 1. The maximum amount of additional resource available is one unit (i.e., b = 1), and the unrestricted common due date is seven (i.e., d = 7). The transportation network and an optimal solution of this example are provided in Fig. 2(a and b).

5. Conclusions

The problem considered in this paper is different from the classical parallel machine scheduling problems in that there exist E-T penalties and one additional resource type. Each job requires one machine and at most one unit of additional resource for its processing. If b is the maximum amount of additional resource available in the system at any point in time, it is possible to show that all jobs requiring additional resource can be optimally assigned only to the first b machines. This proof removes the resource constraints so that the problem can be formulated as an assignment problem which can be solved in polynomial time.

In this research, the case of identical parallel machines is studied. With respect to the processing speed, there are two other classes of parallel machines: uniform and unrelated. Uniform machines are characterized by different speed factors, but the processing speed of a machine is the same for all jobs. However, the processing speed of an unrelated machine may be different for each job. It is important to consider scheduling problems with these types of parallel machines. Thus, several interesting directions for future research remain.

Acknowledgement

This research was partially supported by the National Science Foundation under Grant DDM 90-57066.

Biographies

Jose A. Ventura received his Ph.D. in Industrial Engineering from the University of Florida in 1986. Since 1989 he has been at The Pennsylvania State University, where he is currently Professor of Industrial Engineering. His research and teaching interests include mathematical programming, production scheduling, facility layout and location, and machine vision. He is a member of IIE and INFORMS.

Daecheol Kim received his Ph.D. in Industrial and Manufacturing Engineering from The Pennsylvania State University in 1997. He is currently a managing consultant at LG-EDS Systems, Seoul, Korea. His research interests include production scheduling, supply chain management, and design and analysis of manufacturing systems. He is a member of INFORMS.

(1.) Department of Industrial and Manufacturing Engineering, 207 Hammond Building, The Pennsylvania State University, University Park, PA 16802, USA E-mail: javl@psu.edu

(2.) LG-EDS Systems, Yuhwa Securities B/D 19th Floor, 23-7 Yoido-Dong, Youngdungpo-Gu, Seoul, Korea 150-010

References

(1.) Baker, K.R. (1974) Introduction to Sequencing and Scheduling, Wiley, New York.

(2.) Uzsoy, R., Lee, C.Y. and Martin-Vega, L.A. (1992) A review of production planning and scheduling models in the semiconductor industry part I: system characteristics, performance evaluation and production planning. IIE Transactions on Scheduling and Logistics, 24, 47-61.

(3.) Chandru, V., Lee, CY. and Uzsoy, R. (1993) Minimizing total completion time on batch processing machines. International Journal of Production Research, 31, 2097-2121.

(4.) Blazewicz, J. (1987) Selected topics in scheduling theory. Annals of Discrete Mathematics, 31, 1-60.

(5.) Garey, M.R. and Johnson, D.S. (1975) Complexity results for multiprocessor scheduling under resource constraints. SIAM Journal on Computing, 4, 397-411.

(6.) Blazewicz, J., Barcelo, J., Kubiak, W. and Rock, H. (1986) Scheduling tasks on two processors with deadlines and additional resources. European Journal of Operational Research, 26, 364-370.

(7.) Blazewicz, J., Kubiak, W., Rock, H. and Szwarcfiter, J. (1987) Minimizing mean flow-time with parallel processors and resource constraints. Acta Informatica, 24, 5 13-524.

(8.) Baker, KR. and Scudder, G.D. (1990) Sequencing with earliness and tardiness penalties: a review. Operations Research, 38, 22-36.

(9.) Kanet, J.J. (1981) Minimizing the average deviation of job completion times about a common due date. Naval Research Logistics Quarterly, 28, 643-651.

(10.) Blazewicz, J., Cellary, W., Slowinski, R. and Weglarz, J. (1986) Scheduling under resource constraints - deterministic models, in: Annals of Operations Research, Vol 7, Hammer, P.L. (ed.), J.C. Baltzer AG, Basel, Switzerland.

(11.) Bertsekas, D.P. (1991) Linear Network Optimization, Algorithms and Codes, MIT Press, Cambridge, MA.

(12.) Kuhn, N.W. (1955) The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97.

                      Data set for an example problem
j R(j) [p.sub.j]
1  1       2
2  0       1
3  1       3
4  1       2
5  0       1