Home | Business News | Browse by Publication | M | Mathematics of Operations Research

Job shop scheduling with unit processing times.

Article Excerpt
We consider randomized algorithms for the preemptive job shop problem, or equivalently, the case in which all operations have unit length. We give an [alpha]-approximation for the case of two machines where [alpha] < 1.45, an improved approximation ratio of O(log m / log log m) for an arbitrary number m of machines, and the first (2 + [epsilon])-approximation for a constant number of machines. The first result is via an approximation algorithm for a string matching problem that is of independent interest.

Key words: approximation algorithms; shop scheduling

MSC2000 subject classification: Primary: 90B35; secondary: 68W25

OR/MS subject classification: Primary: production, scheduling; secondary: approximations, heuristic

1. Introduction. Job shop scheduling is a widely studied and difficult combinatorial optimization problem (Lawler et al. [11]). In this problem, we are given a collection of jobs and a set of machines. Each job consists of a sequence of operations, which must be performed in order. Each operation has a particular size and must be performed on a specific machine. The goal is to minimize the makespan, defined as the completion time of the last job to finish. The problem is defined formally in [section] 2.

We consider the preemptive case with the objective to minimize makespan. This problem is strongly NP-hard even for two machines (Gonzalez and Sahni [9]). If the number of machines is part of the input, then the result of Williamson et al. [20] implies that there is no polynomial time approximation algorithm with performance guarantee better than 5/4 unless P = NP.

For the general nonpreemptive job shop scheduling problem, the best-known approximation algorithm has a performance guarantee of O([log.sup.2] m[mu]/[log.sup.2] log m[mu]), where m is the number of machines and [mu] is the maximum number of operations in a job (Shmoys et al. [18], Goldberg et al. [7]). If for every job there is at most one operation on each machine, this bound can be improved to O([log.sup.1+[epsilon]] m) for every [??] > (Czumaj and Scheideler [5], Feige and Scheideler [6]). This variant is called the acyclic job shop scheduling problem. In the case of the acyclic job shop with unit processing times for every operation, the famous papers of Leighton et al. [12, 13] give constant factor approximation algorithms.

In the case of the preemptive job shop, an approximation with ratio O(log m[mu]/log log m[mu]) is known (Leighton et al. [12], Shmoys et al. [18], Goldberg et al. [7]). A polynomial time approximation scheme (PTAS) is known for the special case of a constant number of machines and a constant number of operations per job (Jansen et al. [10]) both for the preemptive and nonpreemptive problems.

In this paper, we give the following results for the preemptive job shop scheduling problem:

(i) For m = 2: It is easy to see that any reasonable schedule has an approximation ratio of 2. Sevastianov and Woeginger [17] gave the first nontrivial 1.5 approximation algorithm for m = 2. An algorithm with a tighter approximation guarantee in terms of the maximum machine load L and the maximum job length l, but still 1.5 in the worst case, was given by Anderson et al. [3]. All known approximation results for shop scheduling (other than approximation schemes) use as a lower bound the maximum of L and l. Sevastianov and Woeginger [17] note than any approximation algorithm with ratio better than 1.5 for the two-machine case would require a new nontrivial lower bound on the optimal makespan. In this paper, we give such a result based on the relationship between the preemptive job shop scheduling problem and a string matching problem over the binary alphabet. Our algorithm has an approximation ratio of less than 1.45.

(ii) For arbitrary m: We give an algorithm with an approximation ratio of O(log m/log log m) for m machines. This eliminates the dependence on [mu] in the results of Leighton et al. [12], Shmoys et al. [18], and Goldberg et al. [7]. We give another very simple algorithm that constructs a schedule of length (1 + [??])L + O([mu] log m)[p.sub.max] in the nonpreemptive case and, hence, a schedule of length (1 + [??])L + O(l log m) in the preemptive case (see [section] 2 for the relationship between preemptive job shop and nonpreemptive job shop with unit processing times), where [p.sub.max] is the maximum length of an operation. In some cases this gives a substantially stronger guarantee than Sevastianov's guarantee (Sevastianov [15, 16]) of L + O(m[[mu].sup.3])[p.sub.max]. In particular, if the instance is such that [mu] [less than or equal to] [??]L/log m, then our algorithm gives a (1 + [??]) approximation.

(iii) For constant m: We show how our additive approximation of (1 + [??])L + O(l log m) can be used to give a polynomial time (2 + [epsilon])-approximation algorithm for any constant number of machines. (Note that we allow the number of operations per job to be part of the input.) Previously, no algorithm with an approximation ratio independent of m was known for the problem.

2. Model and notation. In the job shop scheduling problem, there is a set J = {[J.sub.1], ..., [J.sub.n]} of n jobs that must be processed on a given set [??] = {[M.sub.1], ..., [M.sub.m]} of m machines. Each job [J.sub.j] consists of a sequence of [[mu].sub.j] operations [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] that must be processed in order. Operation [O.sub.kj] must be processed on machine [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] during [p.sub.kj] time units. A machine can process at most one operation at a time, and each job may be processed by at most one machine at any time. For a given schedule, let [C.sub.kj] be the completion time of operation [O.sub.kj]. The objective is to find a schedule that minimizes the maximum completion time, [C.sub.max] = [max.sub.kj] [C.sub.kj]. The value of [C.sub.max] is also called the makespan or the length of the schedule.

For a given instance of the job shop scheduling problem, the value of the optimum makespan will be denoted [C.sup.*.sub.max]. For each job j and machine i, [l.sub.ij] is the total amount of work in job j designated for machine i. Let [l.sub.j] = [[summation].sub.i [member of] [??]][l.sub.ij] denote the total length of job j, and let l = [max.sub.j [member of] [??]] [l.sub.j]. Let [L.sub.i] = [[summation].sub.j [member of] [??]][l.sub.ij]...

View this article FREE - Now for a Limited Time, try Goliath Business News
Free for 3 Days!