数理解析研究所講究録1093 巻 1999 年 11-14

11Single Machine Scheduling with Generalized Precedence Relations
Keisuke Tanaka\dagger(田中圭介)

Shao Chin Sung*(宋少秋)

Milan Vlach\ddagger(ミラン・ブラツハ)

Abstract

Single machine scheduling with precedence relations are well studied. In this paper, weextend the standard concept of these precedence relations, and study scheduling problems
with several classes of this extended concept.

1Introduction

We are concern with scheduling jobs,
on a single machine. The feasibility ofschedules is constrained by a given precedence relation, and the objective is to minimize themaximum of given non-decreasing functions of completion times. Lawler [2] designed an $O(n^{2})$time algorithm for this problem when precedence relation is derived from a directed acyclicgraph
as follows. The vertices of represent the indices of jobs. If contains a directededge from to , then the processing ofcan start only after is completed. We called suchprecedence relation traditional.
In this paper, we introduce a wider concept of precedence which we call generalized precedence. We design polynomial time algorithms for the problem described above with several
classes of generalized precedence relations.
The reminder of this paper is divided into three sections. In Section 2, we introduce thegeneralized precedence relations, and compare them to the traditional precedence relations.
Section 3 is intended to give a brief review on Lawler’s algorithm, which our algorithm is basedon. Section 4 provides our algorithm and its analysis.
$n$

$G$

$J_{1},$$J_{2},$$\ldots$$J_{n}$

$G$

$j$

$k$

$G$

$J_{k}$$J_{j}$$\dot{r}elaiionS$

2

Generalized precedence relations

We begin with a simple example. Suppose we have three jobs
, and the following
traditional precedence relation among them: $G=(V, E)=(\{1,2,3\}, \{(1,3), (2,3)\})$ . It implies
that bothandshould be completed before
starts. We can interpret this requirement as
an AND function.
$J_{1},$$J_{1}$$J_{2}$$J_{2},$$J_{3}$$J_{3}$*School of Information Science, Japan Advanced Institute of Science and Technology, Tatsunokuchi, Ishikawa
923-1292, Japan.
jp\dagger NTT Information Sharing Platform Laboratories, 1-1 Hikarinooka Yokosuka, Kanagawa 239-0847, Japan.
$\mathrm{s}\mathrm{o}\mathrm{n}\mathrm{Q}\mathrm{j}\mathrm{a}\mathrm{i}_{\mathrm{B}\mathrm{t}}.\mathrm{a}\mathrm{c}$.

.

jp\ddagger School of Information Science, Japan Advanced Institute of Science and Technology, Tatsunokuchi, Ishikawa
923-1292, Japan. vlachQi
. jp

ke

$i_{\mathrm{S}\mathrm{u}}\mathrm{k}\mathrm{e}\mathrm{Q}\mathrm{i}\mathrm{S}1.\mathrm{n}\mathrm{t}\mathrm{t}.\mathrm{C}\mathrm{O}$$\mathrm{a}\mathrm{i}\mathrm{S}\mathrm{t}.\mathrm{a}\mathrm{c}$12In some situation, it is quite natural that we have an OR function rather than an ANDfunction. If we replace this AND function with an OR function, then the precedence relations
starts. We canshould be completed before
andabove implies that at ast one ofalso replace the function with a threshold function, a weighted threshold function, or even an
arbitrary monotone function. If we have arbitrary monotone functions for precedence relations,$J_{3}$$J_{2}$$J_{1}$$1\dot{\mathrm{e}}$we call these precedence relations generalized.
Furthermore, we allow different (general) monotone functions for different precedence relations, and consider precedence relations in this manner. This also extends the traditional
concept of precedence relations in a different direction.
proposed by Lawler et al. [3].
In the sequel, we follow the standard three-field notation$\alpha|\beta|\gamma$

The first field indicates the number of machines available and their environment. The second
field indicates a number ofjob characteristics including precedence relations. The third field-AND, it implies that the traditional precedence relaindicates an objective function. If-monotonetion is specified. For problems with generalized precedence relations, we putin the second field.
In addition to precedence relations, if $\beta=$ pmtn, it implies that preemtions of jobs are, it implies that release times of jobs are specified.
allowed; if$\alpha$$\gamma$$\beta$$\beta=\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{c}$$\beta=\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{c}$$\beta=r_{j}$3Lawler’s algorithm for

The problem
is to minimize$1|\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{c}-\mathrm{A}\mathrm{N}\mathrm{D}|f\mathrm{m}\mathrm{a}\mathrm{x}$has a particularly simple and elegant solution [2]. The objective, which is defined as follows:$1|\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{c}- \mathrm{A}\mathrm{N}\mathrm{D}|f_{\mathrm{m}}\mathrm{a}\mathrm{x}$$f_{\max}$

fmax$= \max 1\leq j\leq nf_{j}(C_{j})$,are the cost function and the completion time of job , respectively. The costwhere andcan be quite arbitrary and different from one another, providedof the jobs
functionsonly that they are nondecreasing.
be the index set ofjobs without
Let $N=\{1,2, \ldots , n\}$ be the index set of jobs, and let
successors in . For any subset $S\subseteq N$ , let $p(S)= \sum_{j\in S}\dot{p}j$ be the sum of processing timesof an optimal schedule for the jobs
denote the costin , and letof jobssatisfies the following two inequalities:
indexed by . Clearly,$J_{j}$$C_{j}$$f_{j}$$J_{j}’ \mathrm{s}$$f_{j}’ \mathrm{s}$$L\subseteq N$$G$$J_{j}’ \mathrm{s}$$p_{j}’ \mathrm{s}$$S$

Now let

$J_{l}$$S$$f_{\max}$$f_{\max}^{*}(S)$$f_{\max}^{*}(N)$$f_{\max}^{*}(N)$$\geq$$f_{\max}^{*}(N)$$\geq$$\min_{j\in L}fj(p(N))$,$f_{\max}^{*}(N-\{j\})$for all $j\in N$ .

with $l\in L$ be such that$f|(p(N))= \min_{Lj\in}fj(p(N))$.

We have$f_{\max}^{*}(N) \geq\max\{f_{l}(p(N)), f*\max(N-\{l\})\}$.

13

But the right-hand side of this inequality is precisely the cost of an optimal schedule subject tothe condition thatis in the last position. By repeated applications of this rule, one obtains
an optimal schedule in $O(n^{2})$ time.
Here, we present a pseudo-code of Lawler’s algorithm. This returns a resulting scheduleas a permutation, i.e., $A(j)$ is the index of the job in the j-th position for each $1\leq j\leq n$ .
$J_{l}$$A$

Lawler’s Algorithm.

$u arrow\sum_{1\leq j\leq n}pj|$

for $k=n$ down to 1 doFind $L|$
Choose $l\in L$ such that $f_{l}(u)= \min_{j\in L}f_{j}(u)$ ;Update ;$G$.

$uarrow u-p_{l}|$.

$A(k)arrow l|$

od

Output $(A)$end
Here, is updated as follows. Ifjob is assigned to be the last job, then set to a subgraphof itself that generated by $N-\{j\}$ . Notice that, for problem’ it is easy to findandupdate in Lawler’s Algorithm. Lawler’s algorithm has been generalized by Baker,Lawler, Lenstra, and Rinnooy Kan [1! to an $O(n^{2})$ algorithm for, prec-AND,
.
$G$

$G$

$J_{j}$$1|\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{c}-\mathrm{A}\mathrm{N}\mathrm{D}|f\mathrm{m}\mathrm{a}\mathrm{x}$

$L$

$G$

$\mathrm{t}\dot{\mathrm{o}}$$r_{j}|f_{\max}$$1|\mathrm{p}\mathrm{m}\mathrm{t}\mathrm{n}$4Algorithm for$1|\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{c}- \mathrm{m}\mathrm{o}\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{o}\mathrm{n}\mathrm{e}|f\mathrm{m}\mathrm{a}\mathrm{x}$First, let us define feasibility of schedules for the problem

be the monotone function assigned on vertex
is defined on a setof variables such that

$1\leq j\leq n$$h_{k}$$k$

in the directed acyclic graph$G$for. Each$h_{j}$$X_{k}$$X_{k}=\{X_{jk}|(j, k)\in E(G)\}$

Let. Let$1|\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{C}^{-}\mathrm{m}o\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{o}\mathrm{n}\mathrm{e}|f_{\mathrm{m}\mathrm{a}}\mathrm{x}$$A$

be a schedule. Then, the value of each variable$x_{jk}$.

is assigned according to

1 if is completed before
otherwise.
is feasible if for all $j\in N$ ,$h_{j}|_{A}=1$ ,$J_{j}$$x_{jk}|_{A}=\{$$J_{k}$starts on

$A$

$A$

as follows.

.

$0$

Schedule$A$

whereis the value of when the value of each variable inis assigned according to .
Note that the feasibility of schedules for this problem is consistent with one for the problem
with the traditional precedence relation prec-AND, i.e.,
is an AND function for all $j\in N$ .
For the problem’ we use the Lawler’s algorith.m basically. Note that,in this case, the definition of set in Lawler’s algorithm must be modified. Here we define to$h_{j}|A$$A$$X_{j}$$h_{j}$$h_{j}$$1|\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{C}- \mathrm{m}\mathrm{o}\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{o}\mathrm{n}\mathrm{e}|f_{\mathrm{m}\mathrm{a}}\mathrm{x}$

$L$

$L$

14
be the index set of jobs which can be put in the last position. That is, $j\in L$ if for every

$k$

with

$(j, k)\in E(G)$ ,$h_{k}|_{x_{jk}}=0\not\equiv 0$.

’By the same argument for the problem with traditional precedence relations
it is clear that Lawler’s algorithm with the modified also finds an optimal schedule for our.
problemIn the following, we present the procedure for finding and updating for the case thatbe the threshold and the sum
andis a weighted threshold function for every $k\in N$ . Let. Then,be the weight of variableof weights of all variables of , respectively, and let$1|\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{C}^{-}\mathrm{A}\mathrm{N}\mathrm{D}|f\mathrm{m}\mathrm{a}x$$L$$1|\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{c}-\mathrm{m}\mathrm{o}\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{o}\mathrm{n}\mathrm{e}|f_{\max}$

$G$

$L$

$T_{k}$$h_{k}$$h_{k}$$W_{k}$$x_{jk}$$w_{jk}$$h_{k}|_{x_{jk}=0\not\equiv 0}$$\Leftrightarrow$$W_{k}-w_{jk}\geq\tau k$.

or not. Therefore,
Hence, for every $1\leq j,$ $k\leq n$ , we can decide in $O(1)$ time whether
can be found in $O(n^{2})$ time.
is first updated as in Lawler’sis assigned to be the last job. Then,
Suppose job$:=$
assigned on each vertex in is defined byalgorithm, and the monotone functionis also a weighted threshold function for every. It is obvious that the updated’$k\in N-\{j\}$ . Therefore, for the case that all
are weighted threshold functions, the time$h_{k}|_{x_{jk}=0}\not\equiv 0$

$L$

$G$

$J_{j}$$k$$h_{k}$$\dot{h}_{k}|_{x_{jk}}=0$$G$$h_{k}$$h_{k}$$h_{k^{\mathrm{S}}}$

complexity for updating is $O(n^{2})$ .
runs in time
Hence, Lawler’s algorithm with our procedure for finding and updating$O(n^{3})$ . For the case thatis a arbitrary monotone function, the time complexity for initially
one for .
finding and updating
$G$

$L$

$G$

$h_{j}$$h_{j}$$L\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{e}\mathrm{n}\mathrm{d}_{\mathrm{S}.\mathrm{o}\mathrm{n}}$References[1] BAKER, K. R., LAWLER, E. L., LENSTRA, J. K., AND RINNOOY KAN, A. H. G. Preemptive scheduling of a single machine to minimize maximum cost subject to release dates andprecedence constraints. Operations Research 31 (1983), 381-386.
[2] LAWLER, E. L. Optimal sequencing of a single machine subject to precedence constraints.
Management Science 19 (1973), 544-546.

[3] LAWLER, E. L., LENSTRA, J. K., RINNOOY KAN, A. H. G., AND SHMOYS, D. B. Sequencing and scheduling: Algorithms and complexity. In Handbooks in Operations Researchand Management Science, Volume 4–Logistics of Production and Inventory, S. C. Graves,A. H. G. Rinnooy Kan, and P. H. Zipkin, Eds. North-Holland, Amsterdam, 1993, ch. 9,
pp. 445-522.