We consider the routing open shop problem being a natural combination of two classic discrete optimization problems: metric TSP and Open Shop scheduling problem. Jobs are located at the nodes of a transportation network and have to be processed by mobile machines initially located at the depot. Machines have to complete all the operations and return to the depot minimizing the makespan. The problem is known to be NP-hard even in the simplest case with two machines and only two nodes (including the depot). For this case it is known that optimal makespan doesn't exceed 65 times standard lower bound. Our goal is to refine that result specifying the maximal ratio of the optimal makespan to the standard lower bound (so called abnormality ) depending on the jobs' load distribution between two nodes. We propose a new polynomially solvable subcase of the problem under consideration and describe an exact form of the maximal abnormality as a function of the fraction of the total load located outside the depot.
We use the following notation. The processing time of operation Oji of job Jj by machine Mi is denoted by pji, τlk is the distance between nodes vl and vk, J k is the set of indices of jobs located at vk. The completion time of operation Oji in schedule S is denoted by cji(S). The return time of machine Mi in schedule S is defined as Ri(S) =. max (maxk cji(S) + τ0k) and the makespan Rmax(S) =. max Ri(S) is to be minimized over all feasible k j∈J schedules. Notation Rm∗ax(I) is used for the optimal makespan of problem instance I. In case of m = 2 we also use simplified notation M = {A, B} and aj (bj ) instead of both pj1 (pj2) and Oj1 (Oj2). We also describe jobs in this case by Jj = (aj , bj ).
Additionally we need the following notation.
n • ℓi = ∑pji — load of machine Mi, ℓmax = max ℓi — maximal machine load;
j=1 • dj = m ∑pji — length of job Jj , dkmax = max dj — maximal length of job from vk; i=1 j∈Jk • T ∗ — length of the shortest route over graph G (TSP optimum); • ImX — class of all non-trivial instances (i.e. instances with positive standard lower bound) for problem
ROm|G = X|Rmax.
The following standard lower bound was introduced in [Averbakh et al., 2006]:
{ ( k )} R¯ = max ℓmax + T ∗, max dmax + 2τ0k k (1) Definition 1 A feasible schedule S for problem instance I is referred to as normal if Rmax(S) = R¯(I). Instance I is normal if it admits construction of a normal schedule. . Rm∗ax(I) Definition 2 The abnormality of instance I is the ratio α(I) =
. R¯(I) abnormality of class K is α(K) = sup α(I).
I∈K The problem of finding of the abnormality for some class K is very similar to the following Optima Localization Problem. For some class of instances K find minimal value ρ such that ∀I ∈ K . For some class K of instances
Rm∗ax(I) ∈ [R¯(I), ρR¯(I)].
Obviously such value ρ = α(K). The problem is to find that value and to describe an instance from K with maximal abnormality (if any).
The optima localization problem was studied for RO2|G = K2|Rmax in [Averbakh et al., 2005]. It was shown that α (I2K2 ) = 65 . The instance I˜ of RO2|G = K2|Rmax with maximal abnormality contains a single job J1 = (4, 0) at the depot v0 and two equivalent jobs J2 = J3 = (2, 4) at the distant node v1, distance τ =. τ01 = 1. This result was recently generalized on the case of triangular transportation network: it was shown that α (I2K3 ) = 65 [Chernykh & Lgotina, 2016].
The goal of this paper is to refine the optima localization result for RO2|G = K2|Rmax. depending on the load distribution between nodes v0 and v1. Let ∆k =. ∑ dj stands for the load of node vk, ∆ = ∑∆k = ∑ℓi = ∑dj j∈J k is the total load of instance I (in our case ∆ = ∆0 + ∆1). The load distribution parameter for instance I is defined as
. ∆(I) − ∆0(I) δ(I) = ∈ [0, 1].
∆(I) How does the maximal abnormality depend on δ? Consider a function
F (x) =. α {I ∈ I2K2 |δ(I) = x} , x ∈ [0, 1].
( )
The remainder of the paper is organized as follows. Section 2 contains important preliminary results including new sufficient conditions of normality of instance I. The main result on the behavior of the function F (x) is contained in Section 3 (Theorem 10) followed by some conclusions in Section 4.
The idea of instance simplifying by means of job aggregation procedure has been proved to be a useful tool for solving the Optima Localization Problem as well as for describing efficient approximation algorithms. The detailed description of the procedure in application to RO2||Rmax problem can be found in [Chernykh & Lgotina, 2016]. tThheejiodbesawisitthheinfdoilcloewsifnrogm.LKet wKit⊆h Ja ksincogrlerejsopbonJdKtwoistohmperosucebssseitngoftjiombessfrpoKmi =n.od∑evpkj.i.TOhebnviwoeusmlyayansyubfesatistiubtlee j∈K schedule for a simplified instance can be treated as a feasible schedule for the initial instance with the same makespan. The goal is to perform such a transformation preserving the standard lower bound R¯. In this case the abnormality of an instance would not decrease. We use the following definition from [Chernykh & Lgotina, 2016]. Definition 3 A node vt of an instance I of problem RO2||Rmax is referred to as overloaded if ∆t > R¯(I) − 2τ0t. Otherwise the node vt is underloaded.
It is easy to see from (1) that job aggregation of the whole set J t would not increase the standard lower bound if the node vt is underloaded.
Two following theorems were proved in [Chernykh & Lgotina, 2016].
Theorem 1
We can consider a job aggregation procedure at node vk preserving the standard lower bound as a variant of a Bin Packing problem. Indeed the jobs’ lengths serve as objects sizes and value R¯ − 2τ0k as a bin capacity. According to Theorem 2 for any overloaded node vk optimal bin packing takes 2 or 3 bins. In the next subsection we will describe a special case of bin packing problem which has important applications for the optima localization problem of RO2||Rmax.
Input. Bin capacity B, a set E = {e1, . . . , eN } of integer object sizes with additional condition B < ∑ej 6 2B.
Question. Does there exist a feasible packing of E into exactly three bins of size B such that total contents of any pair of bins strictly exceeds B? Definition 4 An input I is referred to as irreducible if the answer to the Irreducible Bin Packing question is positive. Instance I is efficiently irreducible if such a packing can be found in polynomial time. Theorem 3 The IBP problem is NP-complete.
Proof. We will show a reduction from the well-known PARTITION problem.
Input. A set of integers T = {t1, . . . , tk}, ∑tj = 2T .
Question. Does there exist a subset T ′ ⊂ T such that ∑tj = T ?
T ′
Let T = {t1, . . . , tk} be the input of the PARTITION. Transform it into the following input of the IBP: B = 2T − 2, N = k + 1, ej = tj , 1 6 j 6 k, ek+1 = T − 1. Lets prove that the former instance is irreducible iff the partition for initial instance exists.
Suppose the partition exists. Then we may pack object ek+1 into the first bin and separate the rest equally into second and third bins. This packing is obviously irreducible.
From the other hand, suppose that irreducible packing exists. If some bin contains only object ek+1 then that bin has T − 1 of free space and in order for packing to be irreducible both other bins have to contain at least T total amount of objects, hence the partition exists. In other case there can be only single object of size 1 in the same bin with ek+1 (otherwise two other bins would violate the irreducibility). Thus that bin contains T total amount and has T − 2 of free space, therefore each of other bins has to contain at least T − 1 amount. That means that one of them contains exactly T and other T − 1, therefore the partition exists.
Note that for every irreducible instance of the IBP total size of all objects strictly exceeds 23 B although this condition is obviously not sufficient. We present the following sufficient condition of efficient irreducibility. Theorem 4 Let I be an instance of IBP and
N ∑ ej > j=1 have max ej < 12 B. We can pack those objects into three bins using the following algorithm.
j q ∑ ej > 12 B − x. Pack objects ep+1, . . . , eq into the second bin.
j=p+1 1 B + x 6 12 B + max ej < B.
2 j
.
Let Y = q ∑ ej = 12 B − x + y < B.
j=p+1 3. Pack the rest objects into the third bin. Let Z =.
Lets prove that we obtained an irreducible packing. Note that • X + Y = B + y > B, y 6 max ej , therefore Z = j
N ∑ej − B − y > 0; j=1 • Y + Z = • X + Z =
N ∑ej − 2
1 B − x > j=1
N j∑=1 ej − 2 j
1 B − max ej > B; N ∑ej − 2
1 B − y + x > j=1
N j∑=1 ej − 2 j
1 B − max ej > B.
Therefore the packing is irreducible and obtained in linear time.
Note that the condition in Theorem 4 is given in its strongest form: the claim would be wrong with non-strict inequality.
N ∑ ej . j=q+1 2.3
The goal of this subsection is to describe several sufficient conditions of normality in order to discover a necessary condition of abnormality, as strict as possible. We will apply the former condition to our search of the most abnormal instances from various subclasses. We will focus on RO2|G = K2|Rmax problem from now on. We have two sets of jobs (J 0 and J 1) located at the depot and at the distant node respectively. Distance between nodes is denoted by τ . The standard lower bound (1) can be rewritten in the following form:
R¯ = max{ℓmax + 2τ, d0max, d1max + 2τ }.
Note that if ℓmax + 2τ < R¯ then it is easy to construct a normal schedule for the instance given.
There are several sufficient conditions of normality described in [Chernykh & Lgotina, 2017] for RO2|G = tree|Rmax. The one that is of interest for us is the following.
Theorem 5
A useful corollary for our case would be the following: any instance of RO2|G = K2|Rmax with underloaded distant node is normal.
Now consider an instance with overloaded distant node.
Definition 5 Let I be an instance of RO2||Rmax, vk ∈ V . Node vk is referred to as superoverloaded if the following instance of IBP is irreducible:
B = R¯ − 2τ0k, E = {dj |j ∈ J } k .
The meaning is the following: it is possible to perform the job aggregation in vk preserving R¯ into three jobs in such manner that any following job aggregation would with necessity lead to increase of the standard lower bound. It turned out that the existence of superoverloaded node in RO2|G = K2|Rmax implies the normality. Theorem 6 Let I be an instance of RO2|G = K2|Rmax with superoverloaded distant node. Then I is normal. Proof. Lets apply the job aggregation procedure to the depot (we’ll get single job due to Theorem 2) and to the distant node to obtain exactly three jobs there according to the irreducible packing of the underlying IBP. We’ll obtain an instance I′ with the same R¯ (see Theorem 2). Let J0 be the single job from the depot and J1, J2, J3 — jobs from v1. Note that ∀p ̸= q ∈ {1, 2, 3}
dp + dq > R¯ − 2τ.
Without lost of generality let a1 be the smallest processing time among all of operations from v1.
Construct a schedule S1 in the following manner. Let machine A process jobs in order J1, J2, J3, J0, while machine B processes jobs in order J0, J3, J1, J2. Jobs J1 and J2 are processed first by machine A then B, while operations of other jobs are processed in the opposite order. As soon as each machine travels only once from the depot to the distant node and back, if S1 has no idles then S1 is normal. Let it has some idle intervals. Note that (2) and (3) imply b0 + τ + b3 + a3 + τ + a0 < R¯, and operation b3 completes not earlier than a1. That means that the only idle interval in S1 is possible between operations b1 and b2 and in this case
Rmax(S1) = τ + a1 + a2 + b2 + τ.
Construct another schedule S2 in which machine B processes jobs in the same order as in S1, and A processes in sequence J2, J1, J3, J0. Job J1 now is processed first by B then by A, other jobs are processed in the same order as in S1. Again suppose S2 has some idle intervals. In this case Note that a1 6 min{a3, b1} implies
Rmax(S2) = τ + b0 + b3 + max{a3, b1} + a1 + a0 + τ.
Rmax(S1) + Rmax(S2) 6 4τ + ℓ1 + ℓ2 6 2R¯, (3) (4) (5) therefore the best of those schedules is normal.
Note that the conditions of Theorem 6 don’t give us a polynomially solvable subcase because the aggregation of jobs from distant nodes into three irreducible jobs can be hard (see Theorem 3). Although combining them together with some additional conditions (e.g. from Theorem 4) we can obtain such a new polynomially solvable subclass of instances.
The goal of this section is to describe function F (x) = α {I ∈ I2K2 |δ(I) = x}), that is to find an instance with ( maximal abnormality from class {I ∈ I2K2 |δ(I) = x} for each x ∈ [0, 1]. According to Theorems 5 and 6 distant node of any abnormal instance of RO2|G = K2|Rmax has to be overloaded but not superoverloaded. From Theorem 2 we can safely apply job aggregation procedure to any instance as its abnormality wouldn’t decrease. Moreover we can assume that ℓ1 = ℓ2 as soon as we can easily add dummy jobs to make this property hold preserving both R¯ and δ. Summarizing, for each x ∈ [0, 1] there exists an instance Ix of RO2|G = K2|Rmax such that 1. δ(Ix) = x; 3. ℓ1 = ℓ2; 4. R¯(Ix) = ℓmax + 2τ ; 5. α(Ix) = α {I ∈ I2K2 |δ(I) = x}).
( 2. Ix contains single job J0 at the depot and two jobs J1 and J2 at the distant node; In this section we consider only instances with properties 2–4 mentioned above.
Note that if δ(I) 6 0.5 then the distant node is underloaded and therefore (see Theorem 5) I is normal. Indeed δ(I) 6 0.5 implies ∆1 6 ∆0. Assumption ∆1 > R¯ − 2τ would imply ∆ > 2(R¯ − 2τ ) contradicting (2). Therefore F (x) = 1 for each x ∈ [0, 21 ].
The following lemma shows the lower bound on the function F (x) for x ∈ [ 21 , 1].
Lemma 7 1. For x ∈ [ 21 , 43 ], F (x) >
Note that for I(τ ) R¯ = 1 and δ = 21−+24 ∈ [ 21 , 43 ] therefore τ = 24 −+21 . It is easy to show by consideration of all 4δ possible schedules that Rm∗ax(I(τ )) = 1 + 2τ and α(I(τ )) = . 2δ + 1 2. Consider the following series of instances I(ε) with 0 6 ε 6 2:
J0 = (4 − ε, ε), τ = 1, J1 = J2 = (2 + ε, 4).
For I(ε) R¯ = 10 + ε, δ = 68++"" ∈ [ 43 , 54 ] therefore ε = 6−8 . Optimal schedule for this instance has a makespan −1 Rm∗ax(I(ε)) = 12 + ε therefore α(I(ε)) = 3 − 2δ .
2 − δ Now consider δ ∈ [ 54 , 1)and the following instances I(M ), M > 4:
J0 = (2, 2), τ = 1, J1 = J2 = (M, M ).
Here we have R¯ = 2M + 4, δ = MM+1 ∈ [ 54 , 1)and M = 1− . It is easy to observe that Rm∗ax(I(M )) = 2M + 6 therefore α(I(M )) = 3 − 2δ .
2 − δ The remaining case of δ = 1 obviously contains only normal instances which concludes the proof of Lemma.
To prove that this lower bound is in fact tight we’ll need two additional lemmas.
F (x) > 1,
[ 1 , 34 ] , 2x4+x1 , x ∈ 2 32−−2xx , x ∈ [ 34 , 1] .
x ∈ [0, 12 ] , α(I) 6 Case 2: t > 2τ .
In this case we have Lemma 8 ([Kononov, 2012]) For any instance of RO2|G = K2|Rmax there exists a feasible schedule of makespan R¯ + 2τ . Such a schedule can be constructed in linear time O(n).
Lemma 9 Let S be a schedule for instance I ∈ I2K2 in which each machine travels to the distant node exactly ℓmax . once and total idle time of each machine doesn’t exceed t. Then α(I) 6 2 − ℓmax + t Proof. Each machine in schedule S spends exactly 2τ time on travel therefore Rmax(S) 6 ℓmax + 2τ + t. Therefore by Lemma 8 Rm∗ax(I) 6 ℓmax + 2τ + min{t, 2τ }.
Case 1: t 6 2τ .
In this case ℓmax + 2τ + t ℓmax + 2τ = 1 +
t ℓmax + 2τ
Theorem 10 Let F (x) = α ({I ∈ I2K2 |δ(I) = x}). Then
1, x ∈ [0, 0.5], 4x F (x) = 2x + 1 3 − 2x , x ∈ [0.75, 1]. 2 − x
, x ∈ [0.5, 0.75], 4x , x ∈ [ 12 , 34 ] , F (x) 6 23x−+2x1 , x ∈ [ 43 , 1] .
2 − x most t = b0 + b2 − a1 = ℓmax − d1 = α(I′) 6 2 − ℓmℓamxa+x t = 2 − 2 −1 δ .
Apply job aggregation procedure to I according to Theorem 2. If we’ll obtain three irreducible jobs at distant node then it is superoverloaded and I is normal by Theorem 6. Note that in this case we can construct an optimal schedule in constant time as described in the proof of Theorem 6.
Now we have an instance I′ with single job J0 at the depot, two jobs J1 and J2 at the distant node, ℓ1 = ℓ2 = ¯ R − 2τ .
First we’ll prove that α(I′) 6 2 − 2 −1 δ = 3 − 2δ . Without lost of generality let d1 > d2.
Construct a schedule S in the following man2n−erδ. Let machine A process jobs in order J1, J2, J0 and machine B in order J0, J2, J1. Job J1 is processed first by A then by B, other jobs are processed in opposite sequence. Note that each machine travels in S exactly once and machine B doesn’t idle. Machine A in S idles for at ∆2 − d1 6 ∆20 = (1 − δ)ℓmax time units. By Lemma 9 we have 2 Now let’s prove that α(I′) 6 2 − 2δ + 1 =
4δ . Without lost of generality let b1 > a2 (we do not demand 2δ + 1 d1 > d2 this time).
Construct a schedule S1 according to the following partial order of the operations. Let A process jobs in order J1, J2, J0 and B — in order J0, J1, J2. All jobs except J0 are processed first by A then by B. Note that each machine travels exactly once and A doesn’t idle. The possible idle of B doesn’t exceed t = a1 − b0 due to the assumption b1 > a2.
Construct another schedule S2. Let A process jobs in order J0, J1, J2 and B in order J1, J2, J0. All jobs except J0 are processed first by B then by A. Again, each machine travels exactly once. Machine B doesn’t idle. The total idle of machine A doesn’t exceed either t′ = b1 − a0 or t′′ = b1 + b2 − a0 − a1 (the former takes place if there is an idle between operations a1 and a2).
The total idle of at least one of those schedules S1 and S2 doesn’t exceed the following t + max{t′, t′′} = max{d1, b1 + b2} − d0 6 ℓmax − ∆0 2 2 2 ( 1 ) = ∆1 − ℓmax = ℓmax δ − 2 2 .
2 Therefore by Lemma 9, α(I′) 6 2 − 2 +1 which concludes the proof of the theorem. . 4
Theorem 10 gives a more specific result comparing with [Averbakh et al., 2005] (with significantly simpler proof as well). As soon as the proof is constructive we basically described a F (δ)-approximation algorithm for RO2|G = K2|Rmax. Note that F (δ) reaches the extremal value of 65 only at a single point δ = 34 . That means that although the worst-case performance guarantee of our algorithm is the same as in [Averbakh et al., 2005], the actual worst case is now extremely specific.
Theorem 6 can be easily generalized to the case of G = K3 and even to general graph with additional conditions on the superoverloaded node’s location. It would be of interest to extend this research on some more general case of two-machine routing open shop. Note that the optima localization problem is currently solved only for the cases of G = K2 and G = K3. Technique used in this paper can actually help to solve that problem for some more general cases with constant number of nodes, which in turn would lead to description of better approximation algorithms and probably new polynomially solvable subclasses for those cases.
This work was supported by the Russian Foundation for Basic Research, projects 17-01-00170 and 17-07-00513.