Approximation Algorithms for the Open Shop
Problem with Delivery Times

arXiv:1706.02019v1 [] 7 Jun 2017

Imed KACEM∗and Christophe RAPINE†

Abstract
In this paper we consider the open shop scheduling problem where
the jobs have delivery times. The minimization criterion is the maximum lateness of the jobs. This problem is known to be NP-hard, even
restricted to only 2 machines. We establish that any list scheduling algorithm has a performance ratio of 2. For a fixed number of machines,
we design a polynomial time approximation scheme (PTAS) which represents the best possible result due to the strong NP-hardness of the
problem.

Keywords: Scheduling ; Open Shop ; Maximum Lateness ; Approximation ; PTAS

1

Introduction

Problem description. We consider the open shop problem with delivery
times. We have a set J = {1, 2, ..., n} of n jobs to be performed on a set
of m machines M1 , M2 , M3 .... Mm . Each job j consists of exactly m
operations Oi,j (i ∈ {1, 2, ..., m}) and has a delivery time qj , that we assume
non negative. For every job j and every index i, operation Oi,j should be
performed on machine Mi . The processing time of each operation Oi,j is
denoted by pi,j . At any time, a job can be processed by at most one machine.
Moreover, any machine can process only one job at a time. Preemption
of operations is not allowed. We denote by Ci,j the completion time of
operation Oi,j . For every job j, its completion time Cj is defined as the
completion time of its last operation. The lateness Lj of job j is equal to
Cj + qj . The objective is to find a feasible schedule that minimizes the
maximum lateness Lmax , where
∗

LCOMS, Université de Lorraine, Ile du Saulcy, Metz 57000, France. Contact:
imed.kacem@univ-lorraine.fr
†
LGIPM, Université de Lorraine, Ile du Saulcy, Metz 57000, France. Contact :
christophe.rapine@univ-lorraine.fr

1

Lmax = max {Lj }
1≤j≤n

(1)

For any feasible schedule π, we denote the resulting maximum lateness
by Lmax (π). Moreover, L∗max denotes the maximum lateness of an optimal
solution π ∗ , that is, L∗max = Lmax (π ∗ ). According to the tertiary notation,
the problem is denoted as O||Lmax .
Recall that a constant approximation algorithm of performance ratio
γ ≥ 1 (or a γ-approximation) is a polynomial time algorithm that provides a
schedule with maximum lateness no greater than γL∗max for every instance.
A polynomial time approximation scheme (PTAS) is a family of (1 + ε)approximation algorithms of a polynomial time complexity for any fixed
ε > 0. If this time complexity is polynomial in 1/ε and in the input size
then we have a fully polynomial time approximation scheme (FPTAS).
Related approximation results. According to the best of our knowledge, the design of approximation algorithms has not yet been addressed
for problem O||Lmax . However, some inapproximability results have been
established in the literature. For a fixed number of machines, unless P=NP,
problem Om||Lmax cannot admit an FPTAS since it is NP-hard in the strong
sense on two machines [8], [9]. The existence of a PTAS for a fixed m is
an open question, that we answer positively in this paper. If the number m of machines is part of the inputs, Williamson et al [11] proved that
no polynomial time approximation algorithm with a performance guarantee
lower than 5/4 can exist, , unless P=NP, which precludes the existence of a
PTAS. Several interesting results exist for some related problems, mainly to
minimize the makespan :
• Lawler et al [8]-[9] presented a polynomial algorithm for problem
O2|pmtn|Lmax . In contrast, when preemption is not allowed, they
proved that problem O2||Lmax is strongly NP-hard, as mentioned above.
• Gonzales and Sahni [4] proved that problem Om||Cmax is polynomial
for m = 2 and becomes NP-hard when m ≥ 3 .
• Sevastianov and Woeginger [10] established the existence of a PTAS
for problem Om||Cmax when m is fixed.
• Kononov and Sviridenko [7] proposed a PTAS for problem Oq(P m)|rij |Cmax
when q and m are fixed.
• Approximation algorithms have been recently proposed for other variants such as the two-machine routing open shop problem. A sample
of them includes Chernykh el al [2] and Averbakh et al [1].

2

Finally, we refer to the state-of-the-art paper on scheduling problems under
the maximum lateness minimization by Kellerer [6].
Contribution. Unless P=NP, problem Om||Lmax cannot admit an FPTAS since it is NP-hard in the strong sense on two machines. Hence, the
best possible approximation algorithm is a PTAS. In this paper, we prove
the existence of such an algorithm for a fixed number of machines, and thus
gives a positive answer to this open problem. Moreover, we provide the analysis of some simple constant approximation algorithms when the number of
machines is a part of the inputs.
Organization of the paper. Section 2 present some simple preliminary approximation results on list scheduling algorithms. In Section 3, we
describe our PTAS and we provide the analysis of such a scheme. Finally,
we give some concluding remarks in Section 4.

2

Approximation Ratio of List Scheduling Algorithms

List scheduling algorithms are popular methods in scheduling theory. Recall
that a list scheduling algorithm relies on a greedy allocation of the operations
to the resources that prevents any machine to be inactive while an operation
is available to be performed. If several operations are concurrently available,
ties are broken using a priority list. We call a list schedule the solution produced by a list scheduling algorithm. We establish that any list scheduling
algorithm has a performance guarantee of 2, whatever its priority rule. Our
analysis relies on 2 immediate lower bounds, namely the conservation of the
work and the critical path. Let us denote
n
m
X
X
P = max {
pij } and Q = max {
pij + qj }
i=1,...,m

j=1,...,n

j=1

i=1

Clearly L∗max ≥ P and L∗max ≥ Q. We have the following result :
Proposition 1 Any list scheduling algorithm is a 2-approximation algorithm for problem O||Lmax . More precisely, for any list schedule π, Lmax (π) ≤
P +Q
Proof. Consider a list schedule π, and let u be a job such that Lu =
Lmax (π). Without loss of generality, we can assume that the last operation
of u is scheduled on the first machine. We consider 2 cases : either an idletime occurs on M1 before the completion of job u, or not. If there is no
idle time on M1 , then Lu ≤ P + qu ≤ P + Q. Otherwise, let us denote by
I the total idle time occuring on M1 before the completion time of job u.
We have Lu ≤ P + I + qu . Notice that job u could not have been available
3

on machine M1 at any idle instant, otherwise, due to the principle of list
scheduling algorithms, it would have been scheduled. As a consequence, an
operation of job u is performed on another machine at every idle instant of
M1 before Cu . Hence, we can bound the idle time I by the total processing
time of job u. We have :
Lu ≤ P + I + qu ≤ P +

m
X

piu + qu ≤ P + Q

i=1

We can conclude that in any case Lmax (π) ≤ P + Q ≤ 2L∗max
Notice that good a posteriori performances can be achieved by a list
scheduling algorithm, for instance if the workload P is large compared with
the critical path Q. One natural question is whether some better approximation ratios can be obtained with particular lists. It is a folklore that
minimizing the maximum lateness on one ressource can be achieved by sequencing the tasks in non-increasing order of their delivery times. This
sequence is known as Jackson’s order. One can wonder if a list scheduling
algorithm using Jackson’s order as its list performed better in the worst case.
The answer is negative. The following proposition states that the analysis
of Proposition 1 is tight whatever the list.
Proposition 2 No list scheduling algorithm can have a performance ratio
less than 2 for problem O2||Lmax .
Proof. Consider the following instance: we have 3 jobs to schedule on
2 machines. Jobs 1 and 2 have only one (non null) operation to perform,
respectively on machine M1 and M2 . The duration of the operation is equal
to a time units, where a ≥ 1 is a parameter of the instance. Both delivery
times are null. Job 3 has one unit operation to perform on each machine,
and its delivery time is q3 = a.
An optimal schedule sequences first Job 3 on both machines, creating an
idle time at the first time slot, and then performs Jobs 1 and 2. That is, the
optimal sequence is (3, 1) on M1 and (3, 2) on M2 . The maximum lateness
is equal to L∗max = a + 2. Notice that this schedule cannot be obtained by a
list scheduling algorithm, since an idle time occurs at the first instant while
a job (either 1 or 2) is available. Indeed, it is easy to see that, whatever
the list, either Job 1 or Job 2 is scheduled at time 0 by a list scheduling
algorithm. As a consequence, Job 3 cannot complete before time a + 1 in
a list schedule π. Hence, Lmax (π) ≥ 2a + 1. The ratio for this instance is
2a+1
a+2 , which tends to 2 when a tends to +∞.
As a conclusion, Jackson’s list does not perform better that any other
list in the worst case. Nevertheless, we use it extensively in the PTAS that
we present in the next section.

4

Optimal schedule:
3

1

3

M1

M2

2

Jackson’s schedule:
1

3

3

2

M1

M2

Figure 1. Illustration of the worst case of Jackson's rule

5

3

PTAS

In this section, we present the first PTAS for problem Om||Lmax , that is,
when the number of machines is fixed. Our algorithm considers three classes
of jobs as introduced by Sevastianov and Woeginger [10] and used by several
authors for a variety of makespan minimization in shops (see for instance
the extension by Jansen et al.for the job shop [5]). Notice that our approximation algorithm does not require to solve any linear program.

3.1

Description of the Algorithm

Let ε be a fixed positive number. We describe how to design an algorithm,
polynomial in the size of the inputs, with a performance ratio of (1 + ε)
ε
for problem Om||Lmax . As a shorthand, let ε = 2m(m+1)
. Recall that
P
n
m
P = maxi=1 { j=1 pij } is the maximal workload of a machine. For a given
integer k, we introduce the following subsets of jobs B, S and T :

B=

m

k



j ∈ J | max pi,j ≥ ε P

(2)

i=1



m

j ∈ J | εk P > max pi,j ≥ εk+1 P
i=1


m
k+1
T = j ∈ J | ε P > max pi,j
S=



i=1

(3)
(4)

By construction, for any integer k, sets B, S and T define a partition of
the jobs. For the ease of understanding, the jobs of B will be often called
the big jobs, the jobs of S the small jobs, and the jobs of T the tiny jobs.
Notice that the duration of any operation of a small jobs is less than εk P ,
and less than εk+1 P for a tiny job. The choice of k relies on the following
proposition, which comes from Sevastianov and Woeginger [10]:
Proposition 3 [10] There exists an integer k ≤ d m
ε e such that
p(S) ≤ εP

(5)

P
P
where p(S) = j∈S m
i=1 pij is the total amount of work to perform for the
jobs of S. Moreover, for the big jobs, we have:
|B| ≤

m
εk

(6)

Proof. Let us denote z = dm/εe. Observe that for a given value k, the
duration of the largest operation of any small job belongs to the interval
Ik = [εk+1 P, εk P [. Assume for the sake of contradiction that, for all values
k = 1, . . . , z, the corresponding set Sk does not verify Condition (5). As
6

a consequence, p(Sk ) > εP for each k = 1, . . . , z. Since these sets are
disjoint, it results that the total processing time of the operations
 z+1 of the
jobs whose the duration of its largest operation belongs to ∈ ε P, P is
strictly greater than zεP . However, this amount of work is bounded by the
total work of the instance. We have :
m X
n
X
zεP <
pij ≤ mP
i=1 j=1

Thus z < m/ε, which contradicts our definition of z. It follows that at least
one interval Ik =[εk+1 P, εk P [ with 1 ≤ k ≤ z is suitable to contain the values
of the large operations of subset S such that p(S) ≤ εP .
To prove Inequality (6), we can observe that the total processing time
of the operations of B is bounded by mP . Thus, |B| εk P ≤ mP must hold
and Inequality (6) follows.
Notice that, for a fixed value m of machines, only a constant number
dm/εe of values must be considered for k. Hence, an integer k verifying
the conditions of Proposition 3 can be found in linear time. Assume from
now that k has been chosen according to Proposition 3. In order to present
our approach, let us explain how the different sets S, B and T of jobs
are scheduled in our PTAS. Since set S represents a very small work, we
can schedule it first. Clearly, its last operation cannot complete after time
t(S) ≤ εP in a list schedule. Since set B has a fixed number of jobs, we can
afford to consider all the ways to sequence them. For that, we discretize the
time, considering a time step δ = εk+1 P . Finally, for each assignment of
the big jobs, we schedule the tiny jobs using simply Jackson’s list scheduling
algorithm. One originality of our approach is the possibility for a tiny job
to push a big job in order to fit before it. More precisely, if the tiny job the
list scheduling algorithm is considering cannot complete before the start of
the next big job on its machine, say b, then we force its schedule by shifting
right the operation of job b as much as necessary. This shifting is special
in twofolds : first, we also shift right of the same amount of time all the
operations of the big jobs starting after job b. Second, the operation of job
b is then frozen, that is, it cannot be pushed again by a tiny job. Hence, an
operation of a big job can be pushed at most once by a tiny job, but can be
shifted right a lot of times, due to the push of other operations of some big
jobs. A more formal description of our algorithm can be given as follows:
ALGORITHM PTAS
1. Schedule first jobs of S using any list scheduling algorithm between
time 0 to time p(S) (the cost factor of this simplification will not be
more than 1 + ε).
2. Let δ = εk+1 P . Consider all the time intervals between p(S) and mP
of length δ (the number of these intervals is a constant for a fixed ε).
7

3. Enumerate all the schedules of jobs in B between p(S) and mP . Here,
a schedule is reduced to an assignment of the operations to starting
times of the time intervals defined in the previous step (the cost factor
of this simplification will not be more than 1 + ε).
4. Complete every partial schedule generated in the last step by adding
the jobs of T . The operations of T are added by applying a list scheduling algorithm using Jackson’s order (i.e., when several operations are
available to be performed we start by the one of the largest delivery
time). Note that if an operation cannot fit in front of a big job b, then
we translate b and all the next big jobs by the same necessary duration
to make the schedule feasible. The operation of job b is then frozen,
and cannot be shifted any more.
5. Return the best feasible schedule found by the algorithm.

3.2

Analysis of the Algorithm

We start by introducing some useful notations. Consider a schedule π. For
each machine i, we denote respectively by sir and eir the start time and completion time of the rth operation of a big job on machine i, for r = 1, . . . , |B|.
By convenience we introduce ei0 = 0. For short we call the grid the set of all
the couples (resource × starting time) defined in Phase (2) of the algorithm.
Recall that in the grid the starting times are discretized to the multiples of
δ. Notice that our algorithm enumerates in Phase (3) all the assignments
of big job operations to the grid. Phase (4) consists in scheduling all the
tiny jobs in-between the big jobs. In the following, we call a time-interval
on a machine corresponding to the processing of a big job a hole, for the
machine is not available to perform the tiny jobs. The duration of the rth
hole on machine i, that is eir −sir , is denoted by hir . By analogy to packing,
we call a bin the time-interval between two holes. The duration of the rth
bin on machine i, that is sir − ei,r−1 , is denoted by air . We also introduce
Hir = hi1 + · · · + hir and Air = ai1 + · · · + air , that is the overall duration
of the r first holes and bins, respectively, on machine i.
Now consider an optimal schedule π ∗ . With immediate notations, let
s∗ir be the start time of the rth operations of a big job on the machine i,
and let A∗ir be the overall duration of the r first bins. For the ease of the
presentation, we assume in the reminder, without loss of generality, that
we have no small jobs to schedule : Indeed, Phase (1) does not increase the
length of the schedule by more than εP ≤ εL∗max . We say that an assignment
to the grid is feasible if it defines a feasible schedule for the big jobs. The
next lemma shows that there exists a feasible assignment such that each
operation of the big jobs is delayed, compared to an optimal schedule, by at
least 2mδ time units and by at most (2 + |B|)mδ time units.
8

Lemma 4 There exists a feasible assignment s̄ to the grid such the operations of the big jobs are sequenced in the same order, and for every machine
i and index r we have:
s∗ir + 2mδ ≤ s̄ir ≤ s∗ir + (2 + |B|)mδ
Proof. Among all the possible assignments enumerated in Phase (3) for
the big jobs, certainly we consider the following one, which corresponds to
a shift of the optimal schedule π ∗ restricted to the big jobs :
• Insert 2mδ extra time units at the beginning of π ∗ , that is delay all
the operations by 2mδ.
• Align the big jobs to the grid (shifting them to the right)
• Define the assignment s̄ as the current starting times of the operations
of the big jobs.
More precisely, to align the big jobs to the grid, we consider sequentially
the operations by non-decreasing order of their starting time. We then shift
right the current operation to the next point of the grid and translate the
subsequent operations of the same amount of time. This translation ensures
that the schedule remains feasible for the big jobs.
By construction each operation is shifted right by at least 2mδ time
units, which implies that s̄ir ≥ s∗ir + 2mδ. The alignment of an operation
to the grid again shifts it right, together with all the subsequent operations,
by at most δ time units. Thus, the last operation is not shifted more than
m|B|δ time units by the alignment. The result follows.
Now consider the schedule π obtained by applying the Jackson’s list
scheduling algorithm to pack the tiny jobs between the holes, starting from
the feasible assignment of Lemma 4. Notice that, due to the shift procedure
in Phase (4), the starting time of the big jobs (the holes) can change between
the assignment s̄ and the schedule π. However a hole can be shifted at most
m|B| times since each operation of a big job is shifted at most once by
a tiny job. Moreover the length of a shift is bounded by the duration of
an operation of a tiny job, that is by δ. In addition, as we shift all the
operations belonging to the big jobs, the length of the bins cannot decrease
in the schedule π. Hence, we have the two following properties for the
schedule π, which are direct consequences of Lemma 4 and of the previous
discussion :
1. Any operation of a big job is only slightly delayed compared to the
optimal schedule π ∗ : sir ≤ s∗ir + 2(|B| + 1)mδ
9

2. Each bin is larger in π than in the optimal schedule. More precisely
we have Air ≥ A∗ir + 2mδ for all machine i and all index r.
In other words in the schedule π we have slightly delayed the big jobs to
give more room in each bin for the tiny jobs. We say that a job y is more
critical than a job x if y has a higher priority in the Jackson’s order. By
convention a job is as critical at itself. We have the following lemma:
Lemma 5 In schedule π, for every job x, there exists a job y such that :
qy ≥ qx and Cx ≤ Cy∗ + 2(|B| + 1)mδ
Proof. Let x be a job and Cx its completion time in schedule π. Without
loss of generality we can assume that the last operation of the job x is
processed on the first machine. If x is a big job, that is x ∈ B, we have
already noticed that we have Cx ≤ Cx∗ + 2(|B| + 1)mδ, due to our choice
of the big jobs assignment on the grid. Hence, the inequality of Lemma 5
holds for x. Thus consider in the remaining of the proof the case of a tiny
job x. We denote by Tx the subset of tiny jobs that are more critical than
x and such that their operation on the first machine is completed by time
Cx , that is :
Tx = {y ∈ T | Cy1 ≤ Cx1 and qy ≥ qx }
Observe that our definition implies in particular that x ∈ Tx . We first
establish that in schedule π, almost all the tiny jobs processed before x on
the first machine are more critical than x. That is, the schedule π essentially
follows the Jackson’s sequence for the tiny jobs. Let r be the index of the
bin where x completes in schedule π. For short we denote by A1 (x) the
overall time available for processing tiny jobs on the first machine over the
time-interval [0, C(x)], that is A1 (x) = Cx − H1,r . We also denote by p1 (Tx )
the total processing time of the operations of Tx on the first machine. We
claim that :
p1 (Tx ) ≥ A1 (x) − 2(m − 1)δ

(7)

If at every available instant on the first machine till the completion of x
an operation of Tx is processed in π, then clearly we have A1 (x) = p1 (Tx )
and Inequality 7 holds. Otherwise, consider a time interval I = [t, t0 ], included in a bin, such that no task of Tx is processed. We call such an interval
non-critical for x. It means that during I, either some idle times appear
on the first machine, and/or some jobs less critical than x have been processed. However, due to the shift procedure and the Jackson’s list used by
the algorithm, the only reason for not scheduling x during I is that this job
is not available by the time another less critical job z is started. Notice that
in an open-shop environment, a job x is not available on the first machine
only if one of its operations is being processed on another machine. As a
10

consequence, the interval I necessarily starts during the processing of x on
another machine, that is t ∈ [ti,x , Ci,x ] for some machine i. This holds for
any idle instant and any time an operation is started in interval I. As a
consequence, the interval I cannot finish later than the completion of x on
another machine i0 , plus the duration of a less critical (tiny) job z eventually
started on the first machine during time interval [ti0 ,x , Ci0 ,x ]. Since all the
jobs are tiny,Pthe overall duration of the non-critical intervals for x is thus
bounded by m
i=2 (pi,x +δ), which is at most equal to 2(m−1)δ. Inequality 7
follows.
Now let y be the job of Tx that completes last on the first machine
in the optimal schedule π ∗ . Let r∗ be the index of the bin where y is
processed on the first machine in π ∗ , and let A∗1 (y) be the total available
∗ , that is A∗ (y) = C ∗ − H ∗ .
time for tiny jobs in π ∗ before time C1,y
1
1,y
1,r∗
Recall that r is the number of bins used in schedule π to process all the
operations of Tx on the first machine. We prove that the optimal schedule
also uses (at least) this number of bins, that is r∗ ≥ r. Indeed, by the
conservation of work, we have that A∗1 (y) ≥ p1 (Tx ). Using Inequality 7 we
obtain that A∗1 (y) ≥ A1 (x) − 2(m − 1)δ. By definition of r and r∗ , we also
have A1,r−1 ≤ A1 (x) and A∗1 (y) ≤ A∗1,r∗ . Hence, the following inequality
must hold:
A1,r−1 ≤ A∗1,r∗ + 2(m − 1)δ
However, we have observed that our choice of the assignment of the big jobs
to the grid ensures that for any index l, A∗1,l +2mδ ≤ A1,l , which implies that
we have A1,r−1 + 2δ ≤ A1,r∗ . As a consequence, inequality A1,r−1 < A1,r∗
must hold. Since A1,l represents the total length of the l first bins in π,
which is obviously non-decreasing with l, it implies that r ≤ r∗ .
It means that in π ∗ , task y cannot complete its operation on the first
machine before the first r big tasks. We can conclude the proof of Lemma 5
by writing that, on one hand, Cy∗ ≥ p1 (Tx ) + H1,r , and, on the other hand,
Cx ≤ p1 (Tx ) + 2(m − 1)δ + H1,r . As a consequence, x does not complete
in π latter than 2(m − 1)δ times units after the completion time of y in π ∗ .
Since by definition y is more critical than x, Lemma 5 follows.
Finally, we can conclude that the following theorem holds:
Theorem 6 Problem Om||Lmax admits a PTAS.
Proof. We first establish that the maximum lateness of the schedule returned by our algorithm is bounded by (1 + ε)L∗max . In schedule π defined
in Lemma 5, let u be a job such that Lmax (π) = Cu + qu . If job u is a small
job, then it completes before time p(S). Due to our choice of the partition,
see Proposition 3, we have Lu ≤ εP + qu ≤ (1 + ε)L∗max . Hence, in the
following, we restrict to the case where u ∈
/ S, that is, job u is either a big
11

or a tiny job. According to Lemma 5, there exists a job y such that :
qu ≤ qy and Cu ≤ Cy∗ + 2(|B| + 1)mδ
We have :
Lmax (π) = Cu + qu
≤ Cy∗ + 2(|B| + 1)mδ + qy
≤ L∗max + 2(|B| + 1)mδ
As a consequence, using Proposition 3, we can write that for any fixed
ε≤1:
m
Lmax (π) − L∗max ≤ 2( k + 1)mεk+1 P
ε
m+1
≤ 2( k )mεk+1 P
ε
= 2(m + 1)mεP
≤ εL∗max
Hence, our algorithm has a performance guarantee of (1 + ε). Let us
now check its time complexity. First, the identification of k and the three
2
subsets B, S and T can be done in O( mε.n ). Second, the scheduling of the
jobs of S can clearly be performed in polynomial time (in fact, in linear time
in n for m fixed). Now, let us consider the scheduling of the big jobs. The
number ∆ of points in the grid is bounded by:
∆≤m×
≤

mP
m2
= k+1
δ
ε

m2
m

ε2+ ε
2+ m

ε
2 2m(m + 1)
≤m
ε
The second inequality comes from the fact that k ≤ dm/εe, due to Proposition 3. The last bound is clearly a constant for m and ε fixed. The number
of possible assignments of jobs of B in Phase (3) is bounded by


∆

(m|B|) ≤

m2
εk

∆

Hence, only a constant number of assignments to the grid are to be considered. Phase (4) completes every feasible assignment in a polynomial time.
Phase (5) outputs the best solution in a linear time of the number of feasible assignments. In overall, the algorithm is polynomial in the size of the
instance for a fixed ε and a fixed m.
12

4

Conclusion

In this paper we considered an open question related to the existence of
PTAS to the m-machine open shop problem where m is fixed and the jobs
have different delivery times. We answered successfully to this important
question. This represents the best possible result we can expect due to the
strong NP-hardness of the studied problem.
Our perspectives will be focused on the study of other extensions. Especially, the problem with release dates seems to be very challenging.

References
[1] Averbakh I., Berman O., Chernykh 1., 2005. A 65 -approximation algorithm for the two-machine routing open shop problem on a 2-node
network. European Journal of Operational Research 166(1): 3-24.
[2] Chernykh I., Kononov A., Sevastianov S., 2012. Efficient approximation
algorithms for the routing open shop problem. Computers & Operations
Research
[3] Hall L.A., Shmoys D.B., 1992. Jackson’s rule for single machine scheduling: making a good heuristic better. Mathematics of Operations Research 17: 22:35.
[4] Gonzales T., Sahni S., 1976. Open shop scheduling to minimize finish
time. Journal of Association Computing Machinery 23: 665-679.
[5] Jansen K., Solis-Oba R., Sviridenko M., 2003. Makespan minimization
in job-shops: A linear time approximation scheme. SIAM Journal on
Discrete Mathematics 16(2): 288-300.
[6] Kellerer H (2004) Minimizing the maximum lateness. In: Leung JYT
(ed) Handbook of scheduling: algorithms, models and performance analysis, CRC press, chap. 10.
[7] Kononov A., Sviridenko M., 2002. A linear time approximation scheme
for makespan minimization in an open shop with release dates. Operations Research Letters 30: 276-280.
[8] Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., 1981. Minimizing
Maximum Lateness in a Two-Machine Open Shop. Mathematics of Operations Research 6:153-158.
[9] Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., 1982. Erratum. Mathematics of Operations Research
7(4):635-635.
http://dx.doi.org/10.1287/moor.7.4.635

13

[10] Sevastianov S.V., Woeginger G.J., 1998. Makespan minimization in
open shops: A polynomial time approximation scheme. Mathematical
Programming 82: 191-198.
[11] Williamson D.P. , Hall L.A., Hoogeveen J.A., Hurkens C.A.J., Lenstra
J.K., Sevastianov S.V., Shmoys D.B., 1997. Short shop schedules. Operations Research, 45:288-294

14

