The paper considers a multi-processor tasks scheduling problem with dedicated processors. The main target is determining the tight optima localization intervals for different sub-problems of the basic problem. Based on the ideas of a computer-aided technique developed in the paper by Sevastyanov and Chernykh [15] for shop scheduling problems, we elaborated a similar method for a different-type problem (see above). For small values of the number of processors (from 3 to 5) a computer program coped with the main target. The extremum values of the optimum (in terms of a standard lower bound taken for 1) computed for several sub-problems of the basic problem are listed in Table 1 (page 7). In parallel with those sub-problems, so called prime-versions of those problems were investigated, in which only jobs requiring more than one processor are allowed. An interesting phenomenon was discovered: nearly all (but one) prime-sub-problems appeared to be polynomial-time solvable (with optima coinciding with their lower bounds { such instances and classes of instances were called in [10, 11] normal). As a by-product of those results, a family of lineartime approximation algorithms was designed (for the sub-problems listed in Table 1) with ratio performance guarantees taken from Table 1.
We consider adjacent single mode multiprocessor jobs. Set J = fJ1; :::; Jng of jobs and M of processors are given. Each job has processing time j and may require more than one processor at the same time. We assume that the set of processors required by a job is given and xed. Additionally, we assume that processors are the vertices of a given graph G = (M; E) and the required set of processors must induce a connected subgraph of G: By i M denote the set of processors required by job Ji: Let J A Copyright ⃝c by the paper's authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org denote the set of jobs requiring processors in set A, i.e. J A = fJi : i = Ag. We will say that jobs in set J A are of type A:
A schedule is an assignment of each job Ji to an interval of length i, such that for any two jobs Ji and Jj with i \ j ̸= ∅, their intervals do not overlap. It is required to nd a schedule which minimizes the makespan. For the given graph G we denote the above problem by (G); OP T stands for the optimum.
For any G; (G) is a special case of P jf ixj jCmax [
However, the problem has been given much less attention. Duin and van der
Sluis [
In our paper we present the results on optima localization in terms of lower bounds for different classes of the problem : Two jobs Ji and Jj are called incompatible if i \ j ̸= ∅: Incompatibility of the jobs can be represented as an incompatibility graph. Note that in the incompatibility graphs jobs are represented as nodes. The total processing time of incompatible jobs is a lower bound on OP T: Denote this lower bound by LB(G): Notice that a calculation of LB(G) is equivalent to determining a clique in the incompatibility graph, which is a hard combinatorial problem itself. However, for some special classes of graphs a lower bound can be found in polynomial time. For example, if G is acyclic then a lower bound is easily computable and equal to the maximal processor load.
For the given graph G we wish to nd the minimal functional (G) such that the
inequality OP T (G)LB(G) holds for any instance of (G): We say that a schedule
is primitive if all jobs of the same type are scheduled consecutively. Dell'Olmo et al.
[
Our research is unusual since we use a computer to get the theoretical results. It is
based on the method proposed by Sevastianov and Tchernykh in [
Our paper is organized as follows. We introduce the necessary de nitions and the preliminary results in the second section. In the third section we present a branchand-bound algorithm which calculates (G) and nd an instance I 2 (G) for which OLPBT(J(I)) attains its maximum. In the forth section we list values of (G) for different graphs G obtained by our algorithm. 2
Consider a graph G: Denote the set of valid job types by A(G): Remind that we wish to determine the value of (G): So we need to prove that OP T (I) (G)LB for any instance I of (G) and nd an instance I′ such that OP T (I′) = (G)LB: Lemma 1. For any graph G the supremum of OP T (I)=LB(G) over all instances I; I 2 (G) is attained on an instance which contains at most one job of each type and does not contain jobs required all processors.
Proof is straightforward.
In what follows in this section, we deal with instances that satisfy Lemma 1. We call such instances reduced instances.
As an example, let G be a path with four vertices, i.e. G P4; see Fig. 1. 1 u 2 u 3 u 4 u Thus if G P4 each reduced instance contains at most nine jobs. Without loss of generality we assume that each instance has exactly one job of each valid type. It follows that an incompatibility graph H is the same for all instances of (G): Let A 2 A(G) CTH`QC H`QT#H`QH#`Q#H`Jf2AucH;3AgcHcHcHcHuJf3;4g C T
C#T QQA
Jf2;3;4g
u JCu Jf1g
u
Jf4g we denote by JA and A the job of type A and its processing time, correspondingly. The incompatibility graph for (P4) is shown in Fig. 2.
Let Q H be a maximal clique in H; then ∑JA2V (Q) A is a lower bound on OP T;
where V (Q) is the set of vertices of Q: Generally speaking the number of maximal
cliques grows exponentially in the number of vertices for most graphs. However in our
research we consider graphs with a few number of vertices and we can nd all maximal
cliques in reasonable time. We use the algorithm by Tanaka et al. [
OP T l2 = l3 = OP T l1 = f1g + f1;2g +
f1;2;3g; f2g + f3g + f1;2g + f2;3g + f2;3g + f3;4g + f1;2;3g + f1;2;3g + f2;3;4g; f2;3;4g; l4 = f4g + f3;4g + f2;3;4g:
Thus, LB(P4) = maxfl1; l2; l3; l4g: At this point we assume that LB(G) = 1 and measure all job processing times in these units.
We de ne the weight of each vertex JA in the incompatibility graph H as A: This
graph is called a constraint graph [
It is obvious that different complete paths are critical for different instances. In the next section we propose a branch and bound algorithm to nd (G) by breaking up the set of instances of (G) into smaller subsets, in which instances have the same
Jf2g u Jf1g uXXXXz:Jf1u;2g Jf4g u Jf3g uXXXXzJf3;4g : u
HHHHjJf2;3g * u
J-f1;2;3g u
J-f2;3;4g u critical paths in the selected set of constraint graphs. The algorithm calculates upper and lower bounds on (G) over each subset of instances and use the bounds to discard certain subsets from further consideration. The algorithm starts with (G) = 1 and search the worst instance for which (G) has the maximal value. It terminates when each subset has either produced a solution with the same (G), or has been shown to contain no better solution than the best one found so far by the algorithm. 3
In this section we present a branch and bound algorithm to compute (G) and to nd an instance in which OLPBT( G(I)) attains this value. The algorithm constructs a search tree T: Each vertex v of T contains some subset of instances of (G): Algorithm calculates an upper bound on (G) for this subset. In the calculation of the upper bound algorithm nds the instance, in which the optimal makespan is a lower bound on (G): 3.1
The root v0 contains all instances of (G): Initialize = 1 and (v0) = 1, where is a current lower bound on (G) and (v) is an upper bound on (G) in the vertex v. Take an arbitrary network H 0 and consider a set of complete paths of !H0. We ! remove paths of length less than or equal to : The network on Fig.3 contains two such paths: (Jf2g ! Jf1;2g ! Jf2;3g ! Jf1;2;3g ! Jf2;3;4g) and (Jf3g ! Jf3;4g ! Jf2;3g ! Jf1;2;3g ! Jf2;3;4g):
Let K(!H0) = fp1; p2; : : : ; pjK(!H0)jg be the set of non-trivial paths in the network !H0: We construct jK(!H0)j subsets, one for each path pi 2 K(!H0). The i-th child of v0 contains instances of (G) that have the critical path pi in !H0:
The branching on other vertices in the search tree is similar to previous one. Let v′ be a vertex of the search tree such that (v′) > : Let V be the set of vertices in the v0-v′-path in the search tree. Each vertex v in V corresponds to a critical path in some network chosen during the branching procedure of its parent. By Kv denote the set of such paths. We choose a network !Hv; such that the network !Hv doesn't contain complete paths from Kv: In the next subsection we explain how to choose !Hv correctly. Finally, we use the non-trivial complete paths in !Hv to create children of v:
Let Kv = fp1; : : : ; pN g; and let iA = 1 if a job JA 2 pi and iA = 0 otherwise. Then the length of pi is equal to ∑JA2J iA A: Let be the value of (G) on the set of instances in the vertex v: Then for any pi 2 Kv we have ∑JA2J iA A :
We note that any clique in H forms a (not necessary complete) path in !H: Let KLB be a set of paths corresponding to maximal cliques in H: Then we have ∑JA2J kA A 1 for all pk 2 KLB :
In order to obtain an upper bound (v) on (G) in the vertex v, we solve the following linear program (LP).
∑ A2A(G)
∑ A2A(G) kA A iA A ! max 1; pk 2 KLB
; pi 2 Kv A 0; JA 2 J : (1) (2)
The rational variables A represent processing times of jobs. Inequalities (1) and (2) must hold for any instance I 2 v: Thus an optimal solution of LP nd an instance I′, such that any critical path pi 2 Kv has a length greater than or equal to and this value is the maximum possible. We set (v) = :
If (v) we terminate branching in the vertex v: Otherwise, we construct an optimal schedule for instance I′: If the number of vertices in the graph G is small we can solve an instance I′ in reasonable time. Let be the length of the optimal schedule to the instance I′: First, if < we update the lower bound ; := : Second, if = we terminate branching in the vertex v: Finally, let > : Let a network !Hv correspond to the schedule : Since > ; the network !Hv does not contain paths from the set Kv: We use the network !Hv to branch the vertex v:
The algorithm terminates when (v) for all leaves in current search tree T . Moreover, (v) = for at least one leaf v 2 T . Finally, we obtain (G) = . 4
To present our results we introduce the following notation. We denote the complete graph on n vertices by Kn: By Pn and Cn we denote the path on n vertices and the cycle on n vertices, correspondingly. We also consider the star K1;n on n + 1 vertices and the special graphs shown in Fig. 4.
R1;3: rHHr r r
R1;4: r r rHHr r
r r
A problem (G) is called a prime-version and denoted by (G) if only jobs requiring more than one processor are allowed. Let (G) = maxI2 (G) OLPBT( G(I)) : For each selected graph G we have considered two problems: (G) and (G): The results obtained by the branch and bound algorithm are presented in the Table 1. The rows in Table 1 have the following meaning. Row 1 lists the value of the parameter G in the problem (G): In rows 2 and 3 we present the values of (G) and (G), correspondingly.
(G) (G)
P4 8/7 1
In addition to the results presented in Table 1, we note that (P6) = 1: A comparison of results presented in Table 1 shows that prime-version (G) is easier than the original problem (G): In particular, (G) = 1 means that for any instance I of (G) we have OP T = LB(G): This observation implies a simple exact linear time algorithm for the corresponding problem. Replace all the jobs of the same type by an aggregated job. Set the processing time of the aggregated job equal to the sum of processing times of original jobs. A new instance has a constant number of jobs. We can enumerate all active schedules and choose the best one. In the same way, we obtain a (G)-approximation algorithms for the corresponding problems in the case (G) > 1:
A naive enumeration procedure can be improved by using the search tree T constructed by the branch and bound algorithm when this algorithm calculates (G): Let h be the height of the search tree T: It is sufficient to consider at most h schedules chosen for branching in each vertex in a path from the root v0 to some leaf of T:
We would like to thank Sergey Sevastianov and the anonymous referees for their helpful comments on an earlier draft of this work.
This research is supported by the Russian Science Foundation grant 15-11-10009.