* van der Wel et al. (2014) van der Wel, A., Franx, M., van Dokkum, P. G., et al. 2014, ApJ, 788, 28, doi: 10.1088/0004-637X/788/1/28
  * van Dokkum et al. (2010) van Dokkum, P. G., Whitaker, K. E., Brammer, G., et al. 2010, ApJ, 709, 1018, doi: 10.1088/0004-637X/709/2/1018
  * Wang et al. (2018) Wang, T., Elbaz, D., Daddi, E., et al. 2018, ApJ, 867, L29, doi: 10.3847/2041-8213/aaeb2c
  * Wellons et al. (2015) Wellons, S., Torrey, P., Ma, C.-P., et al. 2015, MNRAS, 449, 361, doi: 10.1093/mnras/stv303
  * Whitaker et al. (2012) Whitaker, K. E., van Dokkum, P. G., Brammer, G., & Franx, M. 2012, ApJ, 754, L29, doi: 10.1088/2041-8205/754/2/L29
  * Whitaker et al. (2011) Whitaker, K. E., Labbé, I., van Dokkum, P. G., et al. 2011, ApJ, 735, 86, doi: 10.1088/0004-637X/735/2/86
  * Whitaker et al. (2017) Whitaker, K. E., Bezanson, R., van Dokkum, P. G., et al. 2017, ApJ, 838, 19, doi: 10.3847/1538-4357/aa6258
  * Williams et al. (2009) Williams, R. J., Quadri, R. F., Franx, M., van Dokkum, P., & Labbé, I. 2009, ApJ, 691, 1879, doi: 10.1088/0004-637X/691/2/1879
  * Williams et al. (2010) Williams, R. J., Quadri, R. F., Franx, M., et al. 2010, ApJ, 713, 738, doi: 10.1088/0004-637X/713/2/738
  * Wuyts et al. (2011) Wuyts, S., Förster Schreiber, N. M., van der Wel, A., et al. 2011, ApJ, 742, 96, doi: 10.1088/0004-637X/742/2/96
  * Zavala et al. (2019) Zavala, J. A., Casey, C. M., Scoville, N., et al. 2019, ApJ, 887, 183, doi: 10.3847/1538-4357/ab5302
  * Zolotov et al. (2015) Zolotov, A., Dekel, A., Mandelker, N., et al. 2015, MNRAS, 450, 2327, doi: 10.1093/mnras/stv740


11institutetext: Minh Hoàng Hà 22institutetext: Trung Thanh Nguyen
33institutetext: ORLab, Faculty of Computer Science, Phenikaa University,
Hanoi 12116, Vietnam
33email<EMAIL_ADDRESS>44institutetext: Dinh Quy Ta
55institutetext: ORLab, Faculty of Information Technology, VNU University of
Engineering and Technology, Hanoi, Vietnam

# Exact Algorithms for Scheduling Problems on Parallel Identical Machines with
Conflict Jobs

Minh Hoàng Hà  Dinh Quy Ta  Trung Thanh Nguyen

(Received: XXXX/XX/XX / Accepted: XXXX/XX/XX)

###### Abstract

Machine scheduling problems involving conflict jobs can be seen as a
constrained version of the classical scheduling problem, in which some jobs
are conflict in the sense that they cannot be proceeded simultaneously on
different machines. This conflict constraint naturally arises in several
practical applications and has recently received considerable attentions in
the research community. In fact, the problem is typically $\mathrm{\bf
NP}$-hard (even for approximation) and most of algorithmic results achieved so
far have heavily relied on special structures of the underlying graph used to
model the conflict-job relation. Our focus is on three objective functions:
minimizing the makespan, minimizing the weighted summation of the jobs’
completion time, and maximizing the total weights of completed jobs; the first
two of which have been intensively studied in the literature. For each
objective function considered, we present several mixed integer linear
programming models and a constraint programming model, from which we can solve
the problems to optimality using dedicated solvers. Binary search-based
algorithms are also proposed to solve the makespan problem. The results of
numerical experiments performed on randomly generated data sets with up to 32
jobs and 6 machines are reported and analysed to verify the performance of the
proposed methods.

###### Keywords:

Machine scheduling conflict job mixed integer linear programming constraint
programming binary search.

##  1 Introduction

The classical scheduling problem on parallel machines (a.k.a minimum makespan)
deals with assigning a set of heterogenous jobs, each having a certain
processing time, to a finite number of identical machines so that the makespan
is minimized, where the makespan is defined as the maximum load over all
machines. While this problem has a long and rich history, its constrained
versions, where additional requirements for the job assignment are attached,
have also flourished in recent years. In this paper we investigate a salient
and remarkable constrained variant in which some jobs are conflict in the
sense that they cannot be processed at the same time (on different machines).
For example, let’s consider a scenario where there is a set of resources, each
with a certain supply, and each job has a specified demand (or request) for
each resource. A conflict occurs among jobs if their accumulative request of a
resource does exceed its supply. The conflict constraint has also arisen in
many other real-word applications such as the load balancing in a parallel
computation BakerC96 , traffic intersection control Bell92 ; Bullock94 , VLSI
and compiler design NicolosoSS99 , frequency assignment in cellular networks
and session management in local area networks HalldorssonKPSST03 , resource-
constrained scheduling GareyG75 .

More recently, several new applications of the conflict constraints are
introduced to demonstrate the situations where some jobs cannot be processed
simultaneously to ensure the reliability of systems. In Ha2019 , the authors
consider a scheduling problem motivated by a joint project with a mobile
network operator, who needs to run various computer programs to adjust
configuration or some parameters of the network. Each program affects a pre-
determined group of mobile subscribers. Any two programs that affect two parts
of the network which have common elements cannot be executed concurrently, and
this can be modeled by the conflict constraints.

Another application can be found in the ROADEF Challenge 2020 named “Grid
operation-based outage maintenance planning” proposed by Réseau de Transport
d’Électricté (RTE), the electricity transmission system operator of France
(see Ruiz ). To guarantee both electricity delivery and supply, RTE must
ensure that the grid is correctly maintained. One of its difficult tasks is to
schedule maintenance operations for its electricity lines. In reality, some
lines are sometimes too close to each other to carry out corresponding
interventions at the same time. This would significantly weaken the network,
and would be dramatic in case another close line is disconnected during the
interventions. Therefore, maintenance jobs corresponding to close lines cannot
be performed simultaneously to ensure the safety of the whole power system.

A simple and widely-used tool for modeling the conflicts among jobs is to make
use of an arbitrary conflict graph, whose vertices correspond to the jobs, and
an edge between two vertices represents the conflict of these two jobs. It is
worth noting that one can also consider the complement of a conflict graph,
called compatible (or agreement) graph, in which there is an edge between two
vertices if the corresponding jobs can be scheduled simultaneously. The
presence of the constraint on conflict jobs makes a machine scheduling problem
more general and harder to address, but worthy to study. The special case of
edgeless graphs (i.e., graphs with no edges) captures exactly the classical
setting where there are no conflict jobs. Beyond conflict graphs, the existing
works in the literature have exhibited scenarios where each conflict may
involve more than two jobs, and the conflict relationships can be expressed by
a general structure such as hypergraphs BlazewiczLK83 . On the other hand,
there has been the case that the processing of some job must be done before
the execution of another job can start, and such a conflict is unable to be
represented in terms of (hyper-)graphs GareyG75 . Our focus in this work is on
the scheduling jobs with pairwise conflicts.

In the literature, machine scheduling problems involving conflict jobs have
been studied under different objectives, including minimum makespan, minimum
weighted-sum of completion times, and maximum total weights of completed jobs.
The first objective, which aims to minimize the amount of time needed for
processing all jobs, has been well-known for decades. The second objective has
been an intuitively appealing objective and studied since the late 1980s and
early 1990s, with a connection to the sum coloring problem Kubicka . The
problem of maximizing the third objective naturally arose as a generalized
version of the classical Knapsack problem (KP) KelPfePis04 , where each job is
associated with a profit and a weight (or length) that specifies the amount of
time that needed to be processed. In this context, every two jobs are conflict
and one may not have them all executed on a single machine, assuming a
deadline $T$ by which the chosen jobs must be finished. We therefore look for
a subset of jobs of maximum total profits that can be scheduled on the
machine.

From a computational point of view, it is important to observe that the
machine scheduling problem with each of the three objectives above is
$\mathrm{\bf NP}$-hard, even for edgeless graphs, meaning that there are no
polynomial time algorithms, unless $\mathrm{\bf P}=\mathrm{\bf NP}$. For
instance, the minimum makespan problem with two identical machines and an
edgeless graph is at least as hard as the Partition problem gar-joh:b:int .
Also, the problem of maximizing total weights of completed jobs on one machine
with deadline $T$ is simply the classical Knapsack problem and is thus
$\mathrm{\bf NP}$-hard. One can see that the conflict graph plays a major
impact on the complexity of the corresponding machine scheduling problem. Most
of the works so far have been therefore concentrated on specific structures of
graphs for which one can either establish $\mathrm{\bf NP}$-harness results as
well as approximation algorithms, or evenly provide polynomial time algorithms
that solve the problem to optimality. An overview of such results is provided
in Section 2.2.

Despite various hardness and approximation results achieved for the machine
scheduling problems with conflict jobs, there has not been much work focusing
on developing exact algorithms for general conflict graphs. Although the
drawback of such algorithms lies on its exponential time, they may still be of
theoretical interest as well as of a practical point of view (we refer to a
survey Woeginger01  by Woeginger for more reasons of studying exact algorithms
for $\mathrm{\bf NP}$-hard problems). In fact, for some realistic situations,
really exact solutions are more preferred than approximate ones. This
motivates us to study in this work potential approaches for exactly solving
the machine scheduling problems with conflict jobs, which, along with known
approximability behaviors, may help understanding better the hardness and the
solvability of the problems.

#### Organization.

The remaining of the paper is structured as follows. In Section 2 we formally
introduce the problem models that are studied in this paper, followed by a
brief overview of related works and our contribution. Section 3 introduces
MILP formulations for the problems, while the CP formulations are described in
Section 4. The algorithms based on binary search for the minimum makespan
problem are discussed in Section 5. The performance comparison of the models
is represented by experimental results in Section 6. Finally, Section 7
concludes our research.

##  2 Problem model and related work

###  2.1 Problem model

Consider a set of $n$ jobs $J=\\{1,\ldots,|J|\\}$ and a set of parallel
identical machines $M=\\{1,\ldots,|M|\\}$. Each job $i\in J$ has a processing
time (or length) $p_{i}\in\mathbb{N}_{>0}$ and can be processed on at most one
machine, without preemptions, that is, once a machine starts processing a job
it continues this processing without interruptions until its completion. We
call jobs of unit processing time unit-jobs. We denote by $p=(p_{i})_{i\in J}$
the vector of job processing times. It is assumed that each machine can
process at most one job at a time. Some of jobs are conflict (or incompatible)
in the sense that they cannot be scheduled simultaneously on different
machines. The conflict relation between jobs is modeled in terms of an
undirected graph $G=(J,E)$, on which each vertex corresponds to a job, and
there is an edge connecting two vertices $i,i^{\prime}$ if they represent two
conflict jobs. In the following we will define an assignment (or schedule) of
jobs to machines. It is assumed that time is discrete and every job and
machine are available for processing at time zero.

######  Definition 1 (Job assignment)

A job assignment (or schedule) is an assignment of time intervals on the
machines to the jobs in such a way that fulfills the following conditions:

  1. 1.

Each job $i$ is assigned an interval of length $p_{i}$ on one machine;

  2. 2.

Every two intervals assigned to the same machine do not intersect;

  3. 3.

For every two conflict jobs, their intervals (on different machines) do not
intersect.

For a job assignment $\pi$, we denote by $s_{i}$ the starting point of an
interval on which a job $i$ is processed on a machine. The interval during
which job $i$ is processed on a machine is $[s_{i},s_{i}+p_{i}]$. Formally,
the job assignment $\pi$ can be defined as a one-to-one mapping:

$\displaystyle\pi:J$ $\displaystyle\rightarrow M\times[0,\mathcal{L}]$
$\displaystyle i$ $\displaystyle\mapsto\pi(i)=(m_{i},s_{i}),$

where $\mathcal{L}=\sum_{i\in J}p_{i}$, such that for every two jobs $i$ and
$i^{\prime}$ we have
$[s_{i},s_{i}+p_{i}]\cap[s_{i^{\prime}},s_{i^{\prime}}+p_{i^{\prime}}]=\emptyset$
if they are conflict or if they are assigned to the same machine, i.e.,
$m_{i}=m_{i^{\prime}}$.

Our definition of job assignment is quite general as it covers both the cases
with and without the deadline constraint. In the former case, where there is a
deadline $T\leq\mathcal{L}$, if there is an allocation $\pi(i)$ with
$s_{i}\geq T$, it means that job $i$ was not assigned to any machine. We
denote by $\Pi$ the set of all possible job assignments $\pi$.

In what follows, we formally define three machine scheduling problems that are
studied in this paper.

######  Definition 2 ($\mathsf{MinMax}$)

Given an instance problem $I=(J,M,p,G)$, compute an assignment $\pi$ such that
jobs are completely processed on machines and the maximum completion time over
all machines is minimized, that is,

$\min_{\pi\in\Pi}\left\\{\max_{i\in J}\\{s_{i}+p_{i}\\}\right\\},$

subject to the conflict constraint. In other words, we seek for a schedule in
which the largest endpoint of an interval assigned to a job is as small as
possible.

######  Definition 3 ($\mathsf{MinSum}$)

In this problem each job $i\in J$ is associated with a nonnegative weight (or
cost) $w_{i}$ beyond the processing time $p_{i}$. Denote by $w=(w_{i})_{i\in
J}$ the vector of job weights. Given an instance problem $I=(J,M,p,w,G)$,
compute an assignment $\pi$ that minimizes the weighted-sum of completion
times, i.e.

$\min_{\pi\in\Pi}\left\\{\sum_{i\in J}w_{i}\cdot(s_{i}+p_{i})\right\\},$

subject to the conflict constraint.

One may assume the number of machines to be infinite, as considered in most of
works in the literature. However, this exactly corresponds to a special case
of our model defined here by setting the number of machines equal to the
number of jobs.

######  Definition 4 ($\mathsf{MaxSum}$)

Similar to $\mathsf{MinSum}$, we assume that in this problem model there is a
vector of job profits $r=(r_{i})_{i\in J}$. In addition, there is a deadline
$T\leq\mathcal{L}$, by which jobs need to be finished. Given an instance
problem $I=(J,M,p,r,G,T)$, compute an assignment $\pi$ that maximizes the
total weights of completed jobs, that is,

$\max_{\pi\in\Pi}\left\\{\sum_{i\in J,s_{i}+p_{i}\leq T}r_{i}\right\\},$

subject to the conflict constraint.

###  2.2 Relate work

This section aims to provide a review of the literature on the three
scheduling problems with conflict jobs: $\mathsf{MinMax}$, $\mathsf{MinSum}$,
and $\mathsf{MaxSum}$. Basically, adding the conflict constraint makes the
scheduling problem much harder to solve, or even to approximate. Hence, most
of work has paid attention on the special structures of the conflict graphs
which can make the problem tractable or approximable. To be more focused, the
review below is separated for each considered problem.

####  $\mathsf{MinMax}$ problem.

One can see that for the edgeless graph (i.e. graph with no edges) all jobs
are not conflict, and $\mathsf{MinMax}$ comes down to the classical minimum
makespan, which is $\mathrm{\bf NP}$-hard. Graham Gr66 ; Gr69  gave a greedy
$3/4$-approximation algorithm for the problem. Hochbaum and Shmoys HochbaumS88
presented a polynomial time approximation scheme111For $\alpha\geq 1$, an
$\alpha$-approximation algorithm for a minimization problem $P$ is a
polynomial time algorithm that can produce a near-optimal solution whose value
is at most $\alpha$ times the optimum. A PTAS is a
$(1+\epsilon)$-approximation algorithm for any fixed constant
$\epsilon\in(0,1)$. We refer to the textbook Vazi01  for more details of
approximation algorithms. (PTAS) and this is the best possible result for the
problem, as it is strongly $\mathrm{\bf NP}$-hard (using a reduction from
3-Partition gar-joh:b:int ). Several exact methods have been proposed for
solving the problem to optimality, including: cutting plane algorithm
Mokotoff04 , branch-and-bound algorithms DellAmicoM05 ; HaouariJ08 , branch-
and-price algorithm DellAmicoIMM08 . For the case of general conflict graphs,
$\mathsf{MinMax}$ with unit jobs was studied under the name mutual exclusion
scheduling by Baker and Coffman BakerC96 . They proved that the problem is
$\mathrm{\bf NP}$-hard in the strong sense if the number of machines is at
least $3$, but is polynomially solvable for the two-machine case, by
constructing a maximum matching for the complement of the conflict graph. The
later positive result was extended by Even et al. EvenHKR09  to the setting
where the length of jobs is $1$ or $2$. Nevertheless, if one allows the job
lengths to take values in domain $\\{1,2,3\\}$, then the problem becomes
$\mathrm{\bf NP}$-hard BendraoucheB12 . Several other works have considered
unit jobs with different structures of the conflict graph alon83 ; Lonc91 ;
BodlaenderJ93 ; Kaller95 ; Jansen03 ; EvenHKR09 . In fact, $\mathsf{MinMax}$
is $\mathrm{\bf NP}$-hard for permutation graphs Jansen03 , complements of
comparability graphs Lonc91 , and for interval graphs BodlaenderJ93 . On the
positive side, Baker and Coffman BakerC96  proved an interesting fact that
$\mathsf{MinMax}$ with unit jobs is equivalent to the so-called $|M|$-bounded
coloring problem222In a $\delta$-bounded coloring problem, one needs to find a
minimum coloring of a given graph such that every color class contains at most
$\delta$ vertices., for which polynomial-time algorithms exist for trees (or
forest) BakerC96 , split graphs and complements of interval graphs Lonc91 ,
cographs and bipartite graphs BodlaenderJ93 , constant treewidth Kaller95 ,
and line graphs alon83 .

Approximability of $\mathsf{MinMax}$ has been investigated for special cases
of job lengths. For example, the case with unit jobs can be expressed as the
$|M|$-Set Cover problem, for which there exists an
$(\mathcal{H}_{|M|}-1/2)$-approximation algorithm DuhF97 , where
$\mathcal{H}_{|M|}=\ln(|M|)+\Theta(1)$, assuming that $|M|$ is constant. When
$|M|$ is part of the input, one cannot approximate the problem to within a
factor of $n^{1-\epsilon}$ Zuckerman06 , for any $\epsilon>0$, unless
$\mathrm{\bf NP}\subset\text{DTIME}(n^{\log\log n})$. For the case when
$p_{i}\in\\{1,2,3\\}$, there is a $4/3$-approximation algorithm EvenHKR09  for
$|M|=2$.

####  $\mathsf{MinSum}$ problem.

As mentioned early, $\mathsf{MinSum}$ (in unweighted form with unit jobs) is
related to the sum coloring problem (SCP) on graphs, which was first studied
by Kubicka Kubicka  in her 1989 thesis (and independently by Supowit Supowit87
in the area of VLSI design). In this problem, colors are positive integers and
the goal is to give to each vertex $i$ of the graph a color $p_{i}$ so that
adjacent vertices have different colors. In this context, the sum of colors
given to the vertices is exactly the sum of completion times of the
corresponding jobs. The minimum value of this sum is well known as the
chromatic sum of the graph. A number of results have been proposed for SCP
(see JinHH17  for a detailed survey). We briefly mention here main algorithmic
results. For general graphs, Bar-Noy et al. Bar-NoyHKSS00  presented an
$\frac{|J|}{\log^{2}(|J|)}$-approximation algorithm, and proved that one
cannot have an approximation factor better than $|J|^{1-\epsilon}$, for any
$\epsilon>0$. In addition, they proved that the problem on line graphs is
$\mathrm{\bf NP}$-hard, but can be approximated to a factor of $2$.
$\mathrm{\bf NP}$-hardness (or inapproximability) results have been also
established for planar graphs HalldorssonK02 , bipartite graphs and perfect
graphs Bar-NoyK98 , and interval graphs G01 . On the positive side, there is a
PTAS for planar graphs HalldorssonK02  (and this even holds for non-unit
jobs), while the approximation factors for bipartite graphs and interval
graphs are, respectively, $\frac{27}{26}$ MJK04  and $1.796$ HalldorssonKS03 .
When jobs are of arbitrary lengths, Gandhi et el. GandhiHKS08  gave improved
factors of $7.682$ for line graphs, and of $11.273$ for interval graphs. Also,
Bar-Noy et al. Bar-NoyK98  proposed a $2.8$-approximation factor for bipartite
graphs and an $O(\log(|N|))$-approximation factor for perfect graphs. Other
$\mathrm{\bf NP}$-hardness results can be found in HoogeveenVV94 ; GiaroKMP01
; Marx03 . Kubicka Kubicka  derived a polynomial time algorithm for trees, and
this was then generalized to graphs of bounded treewidth Jansen97 . Other
conflict graph classes of proper intersection graphs of geometric objects
(e.g. rectangles and disks) have been also studied in BorodinIYZ12 .

To the best of our knowledge, exact methods for $\mathsf{MinSum}$ have been
only proposed for its special case of SCP. The first compact Integer
Programming (IP) model was given in SenDG92 , and its computational results
together with another exponential-size IP model were then studied in
FuriniMMT18 . Very recently, Delle Donne et al. Donea20  have designed the
first branch-and-price algorithm to solve the SCP, using the column generation
technique.

####  $\mathsf{MaxSum}$ problem.

As a special case of $\mathsf{MaxSum}$, the Knapsack problem is known to be
weakly $\mathrm{\bf NP}$-hard and admits a PTAS KelPfePis04 . For the case of
unit jobs, the (weighted) $\mathsf{MaxSum}$ with $T=1$ turns out to be
equivalent to the (weighted) Maximum Independent Set, which cannot be
approximated to within a factor of $n^{1-\epsilon}$, for any $\epsilon>0$, H96
. Hà et al. Ha2019  showed that the problem is polynomially solvable when
there are two machines and the conflict graph is bipartite. In terms of exact
methods, they formulated two mixed integer linear programming models to solve
the problem in the general graph. We are not aware of any other work done so
far for $\mathsf{MaxSum}$, except Ha2019 .

#### Other work.

We would like to mention that there is a number of articles in the literature
concerning with scheduling problems of incompatible jobs, in the sense that
they cannot be performed on the same machine (see, for example BodlaenderJW94
; KowalczykL17 ; MallekBB19 ). This problem is totally different from our
problems studied in this paper.

###  2.3 Our contribution

It is observed that the number of research works focusing on practically
solving the problems with general graphs is quite limited. There are very few
mathematical programming or constraint programming models, from which exact
solution methods can be developed to solve the class of scheduling problems
with conflict jobs. To the best of our knowledge, only in Ha2019 , two mixed
integer linear programming models are proposed to solve the $\mathsf{MaxSum}$
problem to optimality with MILP solvers. There are neither MILP nor CP models
for the $\mathsf{MinMax}$ and $\mathsf{MinSum}$ problems. The lack of exact
methods make the practically computational hardness of the problems be an open
question that is interesting to investigate. To fill these gaps, we take the
first step proposing and analysing in this research several mathematical
models and constraint programming models. In particular, we introduce two new
models, a mixed integer linear programming and a constraint programming, for
the $\mathsf{MaxSum}$ problem. We also adapt existing and new models for the
remaining problems. Using dedicated model solvers, we develop exact algorithms
that can solve the problems to optimality. A binary search technique is also
used to reduce the size of the MILP models proposed for the $\mathsf{MinMax}$
problem and to develop a new exact method. The performance of all these exact
methods is investigated on randomly generated problem instances and several
usage recommendations are provided.

##  3 Mixed integer linear programming models

###  3.1 First formulation (F1)

Let $[K]=\\{1,2,\ldots,K\\}$ be the set of positions that a job can be
processed on a machine. The cardinality of this set can be determined as
$K=\lfloor\frac{T}{p_{\min}}\rfloor$, where $p_{\min}=\min_{i\in J}p_{i}$. The
formulation denoted by (F1) and uses the following variables:

  * •

$x_{imk}$ : binary variables set to $1$ if job $i$ is done by machine $m$ at
$k^{th}$ position

  * •

$s_{i}$: starting time of job $i$

  * •

$z_{mk}$ : the completion time of a job at $k^{th}$ position by machine $m$

  * •

$y_{l}$: binary variables ($l=(i,j)\in C$) used to handle conflict constraint.
It is set to $1$ if job $i$ is finished before starting time of job $j$, and
set to $0$, otherwise.

The $\mathsf{MaxSum}$ problem can be formulated as:

(F1-$\mathsf{MaxSum}$) Maximize $\displaystyle\sum_{i\in J}\sum_{m\in
M}\sum_{k\in K}r_{i}x_{imk}$ (1)
$\displaystyle\text{s.t.}\;\;\;s_{i}+p_{i}\leq T+B(1-$
$\displaystyle\sum_{m\in M}\sum_{k\in K}x_{imk})\quad\forall i\in J$ (2)
$\displaystyle\sum_{m\in M}\sum_{k\in K}x_{imk}\leq 1$
$\displaystyle\quad\forall i\in J$ (3) $\displaystyle\sum_{i\in J}x_{imk}\leq
1$ $\displaystyle\quad\forall m\in M,k\in K$ (4) $\displaystyle z_{m(k-1)}\leq
z_{mk}$ $\displaystyle\quad\forall m\in M,k\in K,k>1$ (5)

$\displaystyle s_{i}+p_{i}\leq z_{mk}+B(1-x_{imk})$ $\displaystyle\quad\forall
i\in J,m\in M,k\in K$ (6) $\displaystyle s_{i}\geq z_{m(k-1)}-B(1-x_{imk})$
$\displaystyle\quad\forall i\in J,m\in M,k\in K$ (7) $\displaystyle
s_{i}+p_{i}\leq s_{j}+By_{l}$ $\displaystyle\quad\forall l=(i,j)\in C$ (8)
$\displaystyle s_{j}+p_{j}\leq s_{i}+B(1-y_{l})$ $\displaystyle\quad\forall
l=(i,j)\in C$ (9) $\displaystyle x_{imk}\in\\{0,1\\}$
$\displaystyle\quad\forall i\in J,m\in M,k\in K$ (10) $\displaystyle
y_{l}\in\\{0,1\\}$ $\displaystyle\quad\forall l=(i,j)\in C$ (11)
$\displaystyle s_{i}\in\mathbb{R^{+}}$ $\displaystyle\quad\forall i\in J$ (12)
$\displaystyle z_{mk}\in\mathbb{R^{+}}$ $\displaystyle\quad\forall m\in M,k\in
K$ (13)

Objective function (1) is to maximize the number of complete jobs with
priorities as highest as possible. Constraints (2) ensure the machine’s
capacity when they enforce every job must be finished before $T$. Constraints
(3) imply each job is processed on no more than one machine at only one
position while constraints (4) make sure that each machine can do at most once
job at one position. Constraints (5) indicate a job must be complete after its
precedence. Constraints (6) and (7) express the relationship among
$z$-variables and the others. Conflict constraints are satisfied by
constraints (8) and (9). Finally, Constraints (10)-(13) define variables’
domain. In this formulation, $B$ is a very large number and can be estimated
by the summation of the capacity and the execution time of all jobs which have
a conflict with other jobs. The number of variables in (F1) is
$|J|.|M|.|K|+|J|+|M|.|K|+|C|$, and that of constraints is
$2.|J|+2.|M|.|K|+|J|.|M|.|K|+2.|C|$.

The $\mathsf{MinSum}$ problem can be modeled as follows:

$\displaystyle\text{(F1-$\mathsf{MinSum}$) \quad\quad Minimize}\;\;\sum_{i\in
J}w_{i}s_{i}$ (14) $\displaystyle\text{s.t.}\;\;\;\sum_{m\in M}\sum_{k\in
K}x_{imk}=1$ $\displaystyle\quad\forall i\in J$ (15)
$\displaystyle(\ref{f1-c3})-(\ref{f1-c12})$

Objective function (14) is to minimize the summation of the weighted start
processing time of all the jobs. This objective function is equivalent to the
function minimizing the weighted completion time of all jobs. Indeed, the
original objective function can be rewritten as $\sum_{i\in
J}w_{i}(s_{i}+p_{i})=\sum_{i\in J}w_{i}s_{i}+\sum_{i\in J}w_{i}p_{i}$. Because
the second term $\sum_{i\in J}w_{i}p_{i}$ is constant, we can remove it from
the objective function without changing the optimal solution. Constraints (15)
ensure that each job must be processed at one position on exactly one machine.
Remaining constraints of the model are taken from formulation
(F1-$\mathsf{MaxSum}$).

To model the $\mathsf{MinMax}$ problem, we use an additional variable
$T_{max}$ representing the completion time of the latest job. The problem can
be stated as follows:

$\displaystyle\text{(F1-$\mathsf{MinMax}$) \quad\quad Minimize}\;\;T_{max}$
(16) $\displaystyle\text{s.t.}\;\;\;T_{max}\geq p_{i}+s_{i}\quad\forall i\in
J$ (17) $\displaystyle(\ref{f1-p2-c2}),(\ref{f1-c3})-(\ref{f1-c12})$
$\displaystyle T_{max}\in\mathbb{R^{+}}$ (18)

Objective function (16) is to minimize the completion time of the latest job.
Constraints (17) imply the relationship of variable $T_{max}$ with other
variables in the model. Constraint 18 defines the domain of variable
$T_{max}$.

###  3.2 Second formulation (F2)

We now present the second MILP model that is denoted by (F2) for the problems.
This model is proposed in Ha2019  and uses three types of variables as
follows:

  * •

$x_{im}$ : binary variables equal to 1 if job $i$ is done by machine $m$

  * •

$s_{i}$: starting time of job $i$

  * •

$y_{ij}$: binary variables equal to 1 if job $i$ is completed before starting
time of job $j$

The problem can be stated as:

(F2-$\mathsf{MaxSum}$) Maximize $\displaystyle\sum_{i\in J}\sum_{m\in
M}r_{i}x_{im}$ (19) $\displaystyle\text{s.t.}\;\;\;s_{i}+p_{i}\leq T+$
$\displaystyle B(1-\sum_{m\in M}x_{im})\quad\forall i\in J$ (20)
$\displaystyle\sum_{m\in M}x_{im}\leq 1$ $\displaystyle\quad\forall i\in J$
(21) $\displaystyle s_{i}+p_{i}\leq s_{j}+B(1-$ $\displaystyle
y_{ij})\quad\forall i,j\in J,i\neq j$ (22) $\displaystyle y_{ij}+y_{ji}\geq
x_{im}+x_{jm}-1$ $\displaystyle\quad\forall i,j\in J,i\neq j,m\in M$ (23)
$\displaystyle y_{ij}+y_{ji}\geq 1$ $\displaystyle\quad\forall(i,j)\in C$ (24)
$\displaystyle x_{im}\in\\{0,1\\}$ $\displaystyle\quad\forall i\in J,m\in M$
(25) $\displaystyle s_{i}\in\mathbb{R^{+}}$ $\displaystyle\quad\forall i\in J$
(26) $\displaystyle y_{ij}\in\\{0,1\\}$ $\displaystyle\quad\forall i,j\in J$
(27)

Similarly to (F1), constraints (20) imply capacity requirements. Constraints
(21) ensure that each job is processed on no more than one machine.
Constraints (22) express the relationship between variables $t$ and $y$.
Constraints (23) say that if two jobs $i$ and $j$ are processed on the same
machine, one job must be completed before starting time of another. They are
used to avoid the overlap among jobs processed on the same machine. Conflict
constraints are assured by constraints (24). Constraints (25)-(27) define
variables’ domain. Similarly to (F1), $B$ in Constraints (21) and (23) is a
very large number and can be estimated by the summation of the capacity and
the execution time of all jobs which have a conflict with other jobs. The
number of variables in the formulation (F2) is $|J|^{2}+|M|.|J|+|J|$, while
the number of constraints is $|J|^{2}+|J|^{2}.|M|+|C|+2.|J|$.

Using this formulation, the $\mathsf{MinSum}$ problem can be formulated as:

(F2-$\mathsf{MinSum}$) Minimize $\displaystyle\sum_{i\in J}w_{i}s_{i}$ (28)
$\displaystyle\text{s.t.}\;\;\;\sum_{m\in M}x_{im}=1$
$\displaystyle\quad\forall i\in J$ (29)
$\displaystyle(\ref{f2-c3})-(\ref{f2-c8})$

Objective function (28) is to minimize the weighted processing start time of
all the jobs. Constraints (29) ensure that each job must be processed on
exactly one machine. Remaining constraints of the model are taken from
formulation (F2-$\mathsf{MaxSum}$). The formulation proposed for the third
problem is:

$\displaystyle\text{(F2-$\mathsf{MinMax}$) \quad Minimize}\;\;T_{max}$ (30)
$\displaystyle\text{s.t.}\;\;\;(\ref{f1-p3-c2}),(\ref{f2-p2-c2}),(\ref{f2-c3})-(\ref{f2-c8})$

###  3.3 Third formulation (F3)

We now introduce a new formulation for the problems. It uses three types of
variables to model the first problem as follows:

  * •

$s_{i}$ : non-negative variable representing the start time of job $i$.

  * •

$x_{imt}$: binary variable equal to one if and only if job $i$ is processed at
time $t$ ($t\in\\{1,...,T\\}$) on machine $m$.

  * •

$z_{i}$: true if and only if job $i$ is scheduled.

The $\mathsf{MaxSum}$ problem can be formulated as:

(F3-$\mathsf{MaxSum}$) Maximize $\displaystyle\sum_{i\in J}r_{i}z_{i}$ (31)
$\displaystyle\text{s.t.}\;\;\;\sum_{i\in J}x_{imt}\leq 1$
$\displaystyle\quad\forall m\in M,\forall t\in\\{1,...,T\\}$ (32)
$\displaystyle\sum_{m\in M}x_{imt}\leq 1$ $\displaystyle\quad\forall i\in
J,\forall t\in\\{1,...,T\\}$ (33) $\displaystyle\sum_{m\in
M}\sum_{t\in\\{1,...,T\\}}x_{imt}=p_{i}z_{i}$ $\displaystyle\quad\forall i\in
J\ $ (34) $\displaystyle t-s_{i}\geq B(\sum_{m\in M}x_{imt}-1)$
$\displaystyle\quad\forall t\in\\{1,...,T\\},\forall i\in J$ (35)
$\displaystyle s_{i}+p_{i}-t-1\geq B(\sum_{m\in M}x_{imt}-1)$
$\displaystyle\quad\forall t\in\\{1,...,T\\},\forall i\in J$ (36)
$\displaystyle\sum_{m\in M}(x_{imt}+x_{jmt})\leq 1$
$\displaystyle\quad(i,j)\in C,t\in\\{1,...,T\\}$ (37) $\displaystyle
x_{imt}\in\\{0,1\\}$ $\displaystyle\quad\forall i\in J,m\in
M,t\in\\{1,...,T\\}$ (38) $\displaystyle s_{i}\in\mathbb{R^{+}}$
$\displaystyle\quad\forall i\in J$ (39) $\displaystyle z_{i}\in\\{0,1\\}$
$\displaystyle\quad\forall i\in J$ (40)

Objective function (31) has the same meaning as functions (1) and (19).
Constraints (32) ensure that on each machine and at a time there is at most
one job is processed. Constraints (33) imply that at a time, each job is
processed on at most one machine. Constraints (34) state that, if job $i$ is
scheduled, its total processing time must be equal to $p_{i}$. The two next
constraints have the meaning as follows: if a job is processed at time $t$,
its start processing time must be less than or equal to $t$ (Constraints 35)
and its completion time must be larger or equal to $t$ (Constraints 36).
Constraints (37) indicate the conflict requirements. The remaining constraints
define the variables’ domains.

In the two remaining problems, parameter $T$ is not defined. However, it is
necessary for the definition of variables $x_{imt}$. Here, we estimate it by a
trivial upper bound on the completion time of the latest job $T=\sum_{i\in
J}p_{i}$.

The $\mathsf{MinSum}$ problem is formulated as:

(F3-$\mathsf{MinSum}$) Minimize $\displaystyle\sum_{i\in J}w_{i}s_{i}$ (41)
$\displaystyle\text{s.t.}\;\;\;\sum_{m\in M}\sum_{t\in\\{1,...,T\\}}x_{imt}$
$\displaystyle=p_{i}\quad\forall i\in J$ (42)
$\displaystyle(\ref{f3-c1}),(\ref{f3-c2}),$
$\displaystyle(\ref{f3-c4})-(\ref{f3-c9})$

Constraints (42) state that the total processing time of job $i$ is must be
equal to $p_{i}$. Finally, we can easily model the $\mathsf{MinMax}$ problem
as follows:

$\displaystyle\text{(F3-$\mathsf{MinMax}$) \quad\quad Minimize}\;\;T_{max}$
(43)
$\displaystyle\text{s.t.}\;\;\;(\ref{f1-p3-c2}),(\ref{f3-c1}),(\ref{f3-c2}),(\ref{f3-c4})-(\ref{f3-c9})$

###  3.4 Comparison of three MILP models

In general, the performance of a MILP formulation partially depends on its
size, which is represented by the number of constraints and variables. In this
section, we compare the three MILP formulations in terms of the number of
constraints and variables. The size of the MILP models depending on the input
data is presented in Table 1.

| (F1) | (F2) | (F3)
---|---|---|---
# of Variables | $\mathcal{O}(|J|.|M|.|K|+|C|)$ | $\mathcal{O}(|J|^{2}+|M|.|J|)$ | $\mathcal{O}(|J|.|M|.T)$
# of Constraints | $\mathcal{O}(|J|.|M|.|K|+|C|)$ | $\mathcal{O}(|J|^{2}.|M|+|C|)$ | $\mathcal{O}(|M|.T+|J|T+|C|T)$
Table 1: Comparison of three MILP models on their size

As can be seen in the table above, the number of constraints and variables in
all three formulations depends on the numbers of jobs $|J|$ and machines $|M|$
of the instance. However, the size of MILP model based on formulation (F2)
depends more on the number of jobs because the numbers of constraints and
variables in (F2) quadratically increase with $|J|$. The number of conflict
job pairs $|C|$ has a significant impact on the number of constraints of all
three formulations, but the impact is larger on the first formulation when the
number of variables in (F1) also depends on $|C|$. The value of $T$, which is
used to compute $|K|$, affects the size of formulations (F1) and (F3).

##  4 Constraint programming models

In this section, we present constraint programming models for the problems.
First, it is worth mentioning that unlike MILP formulations, there is no
standard in CP formulation because it strongly depends on each CP package. In
this study, we formulate the models using generic keywords and syntaxes of IBM
ILOG CP Optimizer CPO . Our model uses the following variables:

  * •

$Itv_{i}$: interval variable that represents the time interval of size $p_{i}$
job $i\in J$ is proceeded.

  * •

$ItvAlt_{im}$: optional interval variable that represents the time interval
machine $m\in M$ proceeds job $i\in J$.

  * •

$Seq_{m}$: sequence variable that represents all working time intervals of
machine $m\in M$.

The $\mathsf{MaxSum}$ problem can be stated as:

(CP-$\mathsf{MaxSum}$) Maximize $\displaystyle\sum_{i\in
J}r_{i}\texttt{presenceOf}(Itv_{i})$ (44)
$\displaystyle\text{s.t.}\;\;\;\texttt{alternative}(Itv_{i},ItvAlt_{im}:m\in
M)$ $\displaystyle\quad\forall i\in J$ (45)
$\displaystyle\texttt{endOf}(Itv_{i})$ $\displaystyle\leq T\quad\forall i\in
J$ (46) $\displaystyle\texttt{noOverlap}(Seq_{m})$ $\displaystyle\quad\forall
m\in M$ (47)
$\displaystyle\big{(}\texttt{endOf}(Itv_{i})\leq\texttt{startOf}(Itv_{j})\big{)}\;\texttt{OR}\;\big{(}\texttt{endOf}(Itv_{j})$
$\displaystyle\leq\texttt{startOf}(Itv_{i})\big{)}\;(i,j)\in C$ (48)

The objective function is represented by (44). Constraints 46) are the
capacity constraints. Next, constraints (47) make sure that jobs processed on
each machine are not overlapped while the conflict constraints are ensured by
constraints (48). Here, the no-overlap constraint noOverlap($s$) on a sequence
variable $s$ states that permutation $s$ defines a chain of non-overlapping
intervals, any interval in the chain being constrained to end before the start
of the next interval in the permutation.

In $\mathsf{MinSum}$ and $\mathsf{MinMax}$ problems, all the jobs must be
processed, the variable $Itv_{i}$ ($i\in J$) is therefore not optional. The
problems are formulated as follows:

(CP-$\mathsf{MinSum}$) Minimize $\displaystyle\sum_{i\in
J}w_{i}\texttt{startOf}(Itv_{i})$ (49) s.t.
$\displaystyle(\ref{cp-c1}),(\ref{cp-c3}),(\ref{cp-c4})$
(CP-$\mathsf{MinMax}$) Minimize $\displaystyle\texttt{max}_{i\in
J}\texttt{endOf}(Itv_{i})$ (50) s.t.
$\displaystyle(\ref{cp-c1}),(\ref{cp-c3}),(\ref{cp-c4})$

##  5 Binary search based algorithms for $\mathsf{MinMax}$ problem

As analysed above, the number of variables and constraints in formulations
(F1) and (F3) heavily depends on the completion time of the latest job $T$.
For the $\mathsf{MinMax}$ problem with the min-max objective function, we can
perform the binary search to reduce the size of $T$ as presented in Algorithm
1. Let $T_{UB}$ and $T_{LB}$ denote an upper bound and a lower bound of $T$.
Recall that the upper bound for any instance can be computed as
$T_{UB}=\sum_{i\in J}p_{i}$. As a result, the lower bound $T_{LB}$ can be
estimated trivially as $T_{LB}=\lceil\frac{T_{UB}}{m}\rceil$. These bounds
provide an initial interval for the binary search. The algorithm then
iteratively solves model (F1-$\mathsf{MinMax}$) or (F3-$\mathsf{MinMax}$) with
$T=T_{MID}$ representing the middle of the current search interval. If a
feasible solution $S$ with the gap returned by MILP solver less than a given
threshold $\gamma$ is found, the upper bound is updated to $obj(S)-1$, since
now it is known that a solution with objective value $obj(S)$ can exist, but
it is not known if a solution with less completion time exists yet. If no
feasible solution is found, the lower bound is set to $T_{MID}+1$, as there
cannot exist any solution with the completion time less than $T_{MID}+1$.
After the loop, the algorithms simply returns the last solution found. This is
sufficient, as the final iteration of the algorithm already proved that any
solution with one less unit of the completion time cannot exist.

It is worth mentioning that the value of $\gamma$ has a significant impact on
the convergence speed of the algorithm. If $\gamma$ is set to a relatively
large number, the running time of an iteration would be quick, but the number
of iterations could be very large. On the other hand, if $\gamma$ is set to a
small value, e.g,. $\gamma$ is set to 0 corresponding to the case where the
MILP models mentioned in Line 5 of Algorithm 1 are required to be solved to
optimality, we can stop the search process as soon as the problem at an
iteration is successfully solved. In this case, the required number of solved
MILP models is the least, but the running time required to process each
iteration could be very large. Therefore, the value of $\gamma$ needs to be
carefully selected so that we get a good trade-off between the number of
required iterations and the running time spent at each iteration. By
experiment, $\gamma$ is set to 10% in this study.

1 $T_{UB}\leftarrow\sum_{i\in J}p_{i};$

2 $T_{LB}\leftarrow\lceil\frac{T_{UB}}{m}\rceil;$

3 while  _$T_{LB}\leq T_{UB}$_ do

4 $T_{MID}=\lfloor(T_{UB}+T_{LB})/2\rfloor;$

5 Solve the corresponding formulation (F1-$\mathsf{MinMax}$) with
$K=\lfloor\frac{T_{MID}}{p_{\min}}\rfloor$ or (F3-$\mathsf{MinMax}$) with
$T=T_{MID}$;

6 if  _a feasible solution S is found_ then

7 $T_{UB}\leftarrow obj(S)-1$;

8

9 end if

10 else

11 $T_{LB}\leftarrow T_{MID}+1$;

12

13 end if

14

15 end while

16return $S$;

Algorithm 1 Binary Search Algorithm

##  6 Experimental Results

In this section, we discuss all our computational experiments with the models
and solution methods proposed above. All algorithms described in this paper
are implemented in C++. The MILP models are solved using CPLEX 12.10.0 and the
CP model is solved with CP Optimizer 12.10.0. All the experiments are done on
a CPU with AMD Ryzen 7 3700X 3.6 Ghz, running on Windows 10. To make ease for
the result reproduction, we use a single thread to solve the models. For a
fair comparison, all the methods are managed to run in a time limit of 1 hour
on each instance.

A total of 432 instances are created using a procedure partly similar to the
one proposed in Ha2019 . They are randomly generated with following
parameters:

  * •

The number of jobs $|J|$ is set to {16, 24, 32}

  * •

The number of machines $|M|$ is set to {2, 4, 6}

  * •

For the $\mathsf{MaxSum}$ problem, the capacity $T$ is set to {10, 20, 40,
80}.

  * •

The priority of each job $i$ is set to a random integer from 1 to 5.

  * •

The weight of each job $i$ is set to a random integer from 1 to 5.

  * •

Two jobs are consecutively considered as conflict with each other in a random
fashion until the number of conflict pairs is equal to $\alpha.n$ where
$\alpha$ is the conflict rate and set to one of four values $\\{1,2,4,8\\}$.
This is generated such that conflict jobs of larger $\alpha$ include those of
smaller $\alpha$.

  * •

The processing time of each job is a random integer from $\lceil T/4\rceil$ to
$\lfloor T/2\rfloor$ (setting 1), from 1 to $\lfloor T/2\rfloor$ (setting 2),
and from 1 to $\lfloor T/8\rfloor$ (setting 3), where $T$ in all three
problems is set to {10, 20, 40, 80}. We note that, for the $\mathsf{MinSum}$
and $\mathsf{MinMax}$ problems, we use the machine capacity $T$ from the
$\mathsf{MaxSum}$ to create the processing time of each job.

To investigate the impact of the instances’ characteristics on the performance
of the models, we report the average values of comparison criteria for each
group of instances depending on the number of jobs, the number of machines,
the machine capacity, the conflict rate, and the processing time settings.
Three main criteria used for the comparison are: the running time in seconds
(Time), the gap between the best lower and upper bounds (Gap), and the number
of instances solved to optimality (Opt).

###  6.1 Results for the $\mathsf{MaxSum}$ problem

We compare four formulations: (F1-$\mathsf{MaxSum}$), (F2-$\mathsf{MaxSum}$),
(F3-$\mathsf{MaxSum}$), and (CP-$\mathsf{MaxSum}$) on the instances of
$\mathsf{MaxSum}$ problem. The results are presented in Table 2. We can derive
several observations as follows:

  * •

In overall, CP performs the best when it can solve to optimality 397 over 432
instances, followed by (F3), (F1), and (F2) with 370, 237, and 198
successfully solved instances, respectively. We also note that there are three
cases where (F3) can solve more instances to optimality than (CP): the
instances with 16 jobs and those with machine capacity equal to 10 or 20.

  * •

The performance of all the formulations tends to decrease when the number of
jobs increases. Formulation (F2) is the most affected. When the number of jobs
increases to 32, the number of successfully solved instances of (F2) is the
least. This could be explained by the fact that the number of variables and
constraints of (F2) is a quadratic function of the number of jobs.

  * •

The performance of (F3) and (CP) is better when the number of machines is
small. However, formulation (F2) tends to work better when the number of
machines increases. The impact of the number of machines on the performance of
(F1) is not really clear.

  * •

The machine capacity has less impact on the performance of formulations (F1),
(F2), and (CP). But the high values of the capacity lead to significant
reduction on the number of successfully solved instances for formulation (F3).
This phenomenon is predictable because the number of variables and constraints
of (F3) depends on the machine capacity.

  * •

Although the number of constraints of all formulations increases when the
conflict rate increases, the performance of the four formulations is
insensitive with the conflict rate. Except for formulation (F1), when the
conflict rate is set to the highest value, the number of successfully solved
instances drastically reduces. This could be due to the fact that only in
formulation (F1), the number of variables increases when the conflict rate
increases.

  * •

Setting 3 of the processing time tends to be easier to solve than the others
for the MILP formulations. On tested instances, the performance of CP is
insensitive to the processing time settings.

Instance | F1 | F2 | F3 | CP
---|---|---|---|---
Time | Gap | Opt | Time | Gap | Opt | Time | Gap | Opt | Time | Gap | Opt
Number of jobs
16 | 1592.5 | 0.0942 | 85 | 495.3 | 0.0095 | 130 | 290.0 | 0.0019 | 138 | 275.816 | 0.0076 | 133
24 | 2111.2 | 0.1498 | 67 | 1973.6 | 0.1939 | 70 | 799.3 | 0.0188 | 119 | 197.816 | 0.0009 | 138
32 | 2482.1 | 0.2526 | 46 | 2694.7 | 0.4690 | 37 | 1004.9 | 0.0465 | 113 | 500.618 | 0.0043 | 126
Number of machines
2 | 2194.4 | 0.2327 | 64 | 2198.8 | 0.4708 | 59 | 315.2 | 0.0014 | 141 | 75.931 | 0.0024 | 141
4 | 2236.7 | 0.1536 | 58 | 1694.4 | 0.1419 | 80 | 799.4 | 0.0255 | 118 | 366.145 | 0.0042 | 131
6 | 1754.7 | 0.1103 | 76 | 1270.4 | 0.0597 | 98 | 979.6 | 0.0402 | 111 | 532.173 | 0.0062 | 125
Machine capacity
10 | 2288.6 | 0.2084 | 42 | 1943.0 | 0.2353 | 53 | 51.5 | 0.0000 | 108 | 191.127 | 0.0062 | 103
20 | 2123.2 | 0.1408 | 49 | 1722.5 | 0.2166 | 59 | 262.6 | 0.0025 | 101 | 415.218 | 0.0023 | 97
40 | 1954.1 | 0.1691 | 53 | 1618.4 | 0.2313 | 63 | 823.1 | 0.0212 | 90 | 359.349 | 0.0051 | 98
80 | 1881.8 | 0.1438 | 54 | 1601.0 | 0.2134 | 62 | 1655.0 | 0.0657 | 71 | 333.306 | 0.0035 | 99
Conflict rate
1 | 1920.7 | 0.1454 | 52 | 1860.0 | 0.2835 | 55 | 577.2 | 0.0066 | 95 | 287.626 | 0.0016 | 100
2 | 1800.8 | 0.1388 | 57 | 1622.0 | 0.2497 | 61 | 555.7 | 0.0067 | 96 | 409.446 | 0.0030 | 97
4 | 1754.9 | 0.1242 | 61 | 1422.1 | 0.1898 | 66 | 734.7 | 0.0137 | 92 | 233.812 | 0.0023 | 103
8 | 2771.4 | 0.2537 | 28 | 1980.7 | 0.1735 | 55 | 924.6 | 0.0625 | 87 | 368.116 | 0.0101 | 97
Processing time settings
1 | 2589.3 | 0.2075 | 48 | 2306.3 | 0.4699 | 57 | 911.1 | 0.0310 | 114 | 531.768 | 0.0046 | 126
2 | 3071.5 | 0.2782 | 25 | 2181.9 | 0.1834 | 63 | 1057.8 | 0.0361 | 112 | 167.461 | 0.0006 | 138
3 | 525.0 | 0.0109 | 125 | 675.3 | 0.0192 | 117 | 125.2 | 0.0000 | 144 | 275.021 | 0.0076 | 133
Total | 2061.9 | 0.1655 | 198 | 1721.2 | 0.2241 | 237 | 698.0 | 0.0224 | 370 | 324.750 | 0.0043 | 397

Table 2: Comparison of different formulations for the $\mathsf{MaxSum}$
problem

###  6.2 Results for the $\mathsf{MinSum}$ problem

Instance | F1 | F2 | F3 | CP
---|---|---|---|---
Time | Gap | Opt | Time | Gap | Opt | Time | Gap | Opt | Time | Gap | Opt
Number of jobs
16 | 2821.8 | 0.3322 | 32 | 2015.2 | 0.1953 | 68 | 2942.7 | 0.5881 | 28 | 1566.780 | 0.3686 | 87
24 | 3520.5 | 0.5246 | 4 | 3304.3 | 0.4507 | 14 | 3297.1 | 0.7779 | 13 | 2877.710 | 0.6860 | 36
32 | 3600.0 | 0.6824 | 0 | 3600.0 | 0.6427 | 0 | 3354.7 | 0.8130 | 11 | 3600.001 | 0.9591 | 0
Number of machines
2 | 3580.0 | 0.7094 | 1 | 3493.5 | 0.6320 | 6 | 3213.7 | 0.7323 | 17 | 3199.712 | 0.8320 | 20
4 | 3329.8 | 0.4902 | 11 | 3031.2 | 0.3984 | 26 | 3229.0 | 0.7347 | 15 | 2575.574 | 0.6370 | 46
6 | 3032.5 | 0.3397 | 24 | 2394.8 | 0.2583 | 50 | 3151.8 | 0.7082 | 20 | 2269.203 | 0.5447 | 57
Machine capacity
10 | 3241.6 | 0.5095 | 12 | 2963.1 | 0.4336 | 21 | 2452.7 | 0.4973 | 36 | 2715.167 | 0.6935 | 29
20 | 3369.0 | 0.5114 | 7 | 2957.1 | 0.4278 | 21 | 3194.7 | 0.6644 | 13 | 2603.880 | 0.6543 | 33
40 | 3276.0 | 0.5202 | 10 | 3021.0 | 0.4375 | 19 | 3549.1 | 0.8387 | 2 | 2666.044 | 0.6575 | 32
80 | 3369.8 | 0.5112 | 7 | 2951.5 | 0.4193 | 21 | 3596.0 | 0.9098 | 1 | 2740.896 | 0.6796 | 29
Conflict rate
1 | 3600.0 | 0.6718 | 0 | 3191.4 | 0.5689 | 13 | 3138.8 | 0.6773 | 15 | 2992.671 | 0.7465 | 21
2 | 3368.6 | 0.4972 | 7 | 2891.9 | 0.4269 | 23 | 3192.4 | 0.7253 | 13 | 2671.296 | 0.6581 | 30
4 | 2737.2 | 0.3579 | 27 | 2312.7 | 0.2880 | 42 | 3203.4 | 0.7601 | 13 | 1896.029 | 0.4837 | 53
8 | 3550.5 | 0.5254 | 2 | 3496.7 | 0.4344 | 4 | 3258.0 | 0.7376 | 11 | 3165.990 | 0.7967 | 19
Processing time settings
1 | 3362.4 | 0.5313 | 10 | 3047.6 | 0.4622 | 23 | 3583.0 | 0.8852 | 1 | 2891.071 | 0.7552 | 30
2 | 3328.7 | 0.5061 | 11 | 2933.7 | 0.4036 | 30 | 3594.8 | 0.8449 | 1 | 2558.680 | 0.6115 | 47
3 | 3251.2 | 0.5018 | 15 | 2938.2 | 0.4229 | 29 | 2416.6 | 0.4517 | 50 | 2594.739 | 0.6470 | 46
Total | 3314.1 | 0.5131 | 36 | 2973.2 | 0.4296 | 82 | 3198.2 | 0.7252 | 52 | 2681.497 | 0.6712 | 123

Table 3: Comparison of different formulations for the $\mathsf{MinSum}$
problem

Table 3 reports the results for the $\mathsf{MinSum}$ problem. We derive
several observations as follows:

  * •

In overall, CP still performs the best when it can solve to optimality 123
over 432 instances. The worst formulation is (F1). Formulation (F2) overcomes
(F3) to become the second best formulation in terms of the number of
successfully solved instances. Formulation (F3) can solve more instances to
optimality than (CP) in two cases: the instances with 32 jobs and the ones
with the third processing time setting.

  * •

The performance of all the formulations tends to decrease when the number of
jobs increases. Formulation (F3) can solve 11 instances of 32 jobs to
optimality, while three formulations (F1), (F2), and (CP) fail to close the
gaps for all these instances.

  * •

Unlike the first problem, the performance of (F1), (F2) and (CP) for the
second problem is better when the number of machines increases. The impact of
the number of machines on the performance of (F3) is not really clear.

  * •

The machine capacity has less impact on the performance of formulations (F1),
(F2), and (CP). But the high values of the capacity lead to significant
reduction on the number of successfully solved instances for formulation (F3).
This phenomenon is predictable because the number of variables and constraints
of (F3) depends on the machine capacity. This observation is similar to the
first problem.

  * •

The performance of (F3) is insensitive with the conflict rate for (F3). For
three remaining formulations, the instances with conflict rate $\alpha=4$ seem
to be the easiest.

  * •

Setting 3 of the processing time tends to be easier to solve than the two
other settings for formulations (F1) and (F3) whose number of variables and
constraints rapidly increases when the value of $T_{max}$ is higher. The
performance of (F2) and (CP) is insensitive to the processing time setting.

###  6.3 Results for the $\mathsf{MinMax}$ problem

We now compare the exact methods based on the four formulations:
(F1-$\mathsf{MinMax}$), (F2-$\mathsf{MinMax}$), (F3-$\mathsf{MinMax}$), and
(CP-$\mathsf{MinMax}$); and the two methods based on the binary search (F1-BS)
and (F3-BS). The obtained results are shown in Table 4 where Columns “Iter”
report the number of iterations the search is performed in the binary search
algorithms.

Instance F1 F2 F3 CP F1-BS F3-BS Time Gap Opt Time Gap Opt Time Gap Opt Time
Gap Opt Time Iter Gap Opt Time Iter Gap Opt Number of jobs 16 2333.9 0.2769 51
2146.8 0.2283 60 1204.4 0.1679 100 908.356 0.2025 108 969.6 3.1 0.1611 107
966.948 3.410 0.2281 109 24 2990.1 0.3262 31 2556.6 0.2833 45 2316.1 0.4294 56
701.881 0.0893 117 1885.7 2.8 0.0943 80 1995.529 1.958 0.8878 68 32 3556.8
0.4837 3 3198.4 0.4378 21 2694.0 0.5517 42 991.753 0.1502 105 2054.2 2.5
0.0788 67 2207.820 1.882 1.1087 60 Number of machines 2 3600.1 0.6038 0 3600.1
0.5636 0 2165.3 0.4015 65 507.402 0.1079 124 1137.5 2.6 0.0742 100 1631.355
2.313 0.1360 82 4 3115.8 0.3236 22 2620.9 0.2677 44 2101.5 0.3956 63 1080.833
0.1924 101 1944.2 2.6 0.1047 75 1808.256 2.313 0.7400 76 6 2164.8 0.1595 63
1680.9 0.1182 82 1947.7 0.3518 70 1013.755 0.1418 105 1827.9 3.3 0.1554 79
1730.686 2.625 1.3487 79 Machine capacity 10 2991.6 0.3950 20 2746.5 0.3454 29
882.7 0.0819 88 511.508 0.0963 93 1282.0 2.1 0.1128 76 455.089 2.019 0.1439 97
20 2914.5 0.3595 22 2593.7 0.3160 32 1860.7 0.3059 55 838.071 0.1496 83 1364.0
2.5 0.1129 72 1513.904 2.435 0.3693 66 40 2940.2 0.3519 22 2656.2 0.3078 32
2437.7 0.4914 37 954.645 0.1661 80 1859.1 3.1 0.1188 57 2195.810 2.546 0.9914
45 80 2994.7 0.3427 21 2539.3 0.2967 33 3104.9 0.6527 18 1165.095 0.1775 74
2041.0 3.6 0.1010 49 2728.927 2.667 1.4617 29 Conflict rate 1 3207.9 0.4434 12
3173.3 0.4233 13 1914.0 0.3359 55 634.180 0.0745 89 506.0 2.3 0.0033 96
1438.842 1.833 0.4285 67 2 2910.2 0.3540 21 2722.3 0.3293 28 1913.7 0.3673 54
622.403 0.0761 90 1023.2 2.7 0.0087 82 1501.743 2.074 0.5299 68 4 2442.2
0.2518 37 2119.8 0.2204 46 2324.3 0.4015 43 616.228 0.0949 90 1513.2 3.4
0.0210 67 1965.017 2.241 0.6854 52 8 3280.6 0.4000 15 2520.4 0.2929 39 2133.9
0.4272 46 1596.509 0.3440 61 3503.7 2.9 0.4126 9 1988.128 3.519 1.3225 50
Processing time settings 1 3099.3 0.3894 21 2779.7 0.3483 36 2833.3 0.5840 34
1275.793 0.2153 94 2040.3 3.1 0.1367 69 2500.681 2.486 1.0661 47 2 2823.3
0.3202 35 2544.1 0.2792 45 2361.2 0.4472 55 847.179 0.1305 111 1625.5 3.3
0.0784 84 2053.826 2.604 0.9771 67 3 2958.1 0.3772 29 2578.0 0.3220 45 1019.9
0.1178 109 479.017 0.0964 125 1243.7 2.1 0.1192 101 615.790 2.160 0.1815 123
Total 2960.2 0.3623 85 2633.9 0.3165 126 2071.5 0.3830 198 867.330 0.1474 330
1636.5 2.8 0.1114 254 1723.433 2.417 0.7416 237

Table 4: Comparison of different methods for the $\mathsf{MinMax}$ problem

From Table 4, several observations are derived as following:

  * •

The binary search algorithms significantly improve the original formulations.
The CP formulation is still the best, followed by (F1-BS) and (F3-BS) in terms
of the number of instances solved to optimality. However, we also observe that
(F3-BS) is better then (CP) on instances with one of two characteristics:
$n=16$ or $T=10$ while (F1-BS) performs better than (CP) on instances with
conflict rate set to 1. Among the three methods based on the pure MILP
formulations, our new model (F3) is the dominant, followed by (F2) and (F1).
Although formulation (F1) performs worse than formulation (F3), the F1-based
binary search algorithm can solve more instances than the algorithm based on
(F3).

  * •

The number of jobs increases, the performance of MILP-based methods (including
binary searches) decreases. The (CP) model is less dependent on the number of
jobs.

  * •

Four methods (F3), (CP), (F1-BS), and (F3-BS) can solve more instances with
the least number of machines that is equal to 2. The performance of two
formulations (F1) and (F2) increases when the number of machines increases.

  * •

The performance of (F1) and (F2) is insensitive with the machine capacity. The
remaining methods can solve more instances to optimality when the machine
capacity is smaller.

  * •

The increase in the number of conflict jobs leads to harder instances for
methods (CP), (F1-BS), and (F3-BS). The instances with more conflict jobs
require more iterations to solve for the two binary search methods. The impact
of the conflict rate on three pure MILP methods is less clear.

  * •

F3-based methods can solve more instances with the setting 3 of the processing
time. The impact of the processing time settings on the performance of the
other methods is not clear.

###  6.4 Other discussions

We now discus the hardness of the three problems based on the performance of
the algorithms. Surprisingly, the min-max objective function which has a non-
linear characteristic does not make the $\mathsf{MinMax}$ problem the most
challenging. Among three problems, the $\mathsf{MinSum}$ problem is the most
difficult for the proposed methods, followed by the $\mathsf{MinMax}$ and
$\mathsf{MaxSum}$.

In terms of the performance on the three problems, (CP) is in overall the best
when it can solve more instances of all the problems than other methods. Among
MILP-based instances, our new formulation (F3) performs better than two
existing formulations (F1) and (F2) in terms of the number of solved
instances.

Although (CP) dominates other formulations, we also note that there are a
number of instances that (CP) cannot solve to optimality while the MILP-based
methods can. As can be seen in Table 5, all the formulations can provide
optimal solutions on several instances that (CP) cannot close the gaps. More
precisely, (F1) and (F2) can solve 2 and 3 instances of the $\mathsf{MinSum}$
problem that are not solved to optimality by (CP). In particular, (F3) can
perform better than (CP) on instances of all problems. Therefore, for the
$\mathsf{MaxSum}$ and $\mathsf{MinSum}$ problems, we recommend to use in
practice the (CP) and (F3) models for exact methods. For the $\mathsf{MinMax}$
problem, the algorithms based on (CP), (F1-BS), and (F3-BS) could be selected
options.

| $\mathsf{MaxSum}$ | $\mathsf{MinSum}$ | $\mathsf{MinMax}$
---|---|---|---
F1 | 0 | 2 | 0
F2 | 0 | 3 | 0
F3 | 23 | 30 | 40
F1-BS |  |  | 10
F3-BS |  |  | 50
Table 5: The number of instances MILP-based methods can solve to optimality
while CP cannot

##  7 Conclusion

We study in this paper a class of three scheduling problems where some jobs
cannot be scheduled concurrently on different machines: $\mathsf{MaxSum}$,
$\mathsf{MinSum}$, and $\mathsf{MinMax}$. We propose two new models based on
mixed integer linear programming and constraint programming for the
$\mathsf{MaxSum}$ problem and adapt these models and two other existing ones
for the $\mathsf{MinSum}$ and $\mathsf{MinMax}$ problems. Corresponding
solvers are used to solve the models to optimality, leading the first exact
methods proposed for the problems. In addition, binary search-based exact
algorithms also are developed for the $\mathsf{MinMax}$ problem. Results of
experiments carried out on instances with up to 32 jobs and 6 machines are
reported and analysed. The performance of new models is clearly better than
that of existing models in terms of the number of instances solved to
optimality. The binary search algorithms for the $\mathsf{MinMax}$ problem
also show their effectiveness.

The research perspectives are numerous. The MILP formulations could be
strengthen with additional valid inequalities or optimality cuts to develop
efficient branch-and-cut algorithms. Metaheuristics could also be developed to
provide good solutions for larger instances in short computation time.
Finally, other variants of scheduling problems (e.g., flow shop, job shop)
with the conflict constraint are interesting topics for other researches.

## Acknowledgment

This work has been supported by Phenikaa University.

## References

  * (1) Alon, N.: A note on the decomposition of graphs into isomorphic matchings.  Acta Mathematica Hungarica 42, 221–223 (1983)
  * (2) Baker, B.S., Coffman, E.G.: Mutual exclusion scheduling.  Theor. Comput. Sci. 162(2), 225–243 (1996)
  * (3) Bar-Noy, A., Halldórsson, M.M., Kortsarz, G., Salman, R., Shachnai, H.: Sum multicoloring of graphs.  J. Algorithms 37(2), 422–450 (2000)
  * (4) Bar-Noy, A., Kortsarz, G.: Minimum color sum of bipartite graphs.  J. Algorithms 28(2), 339–365 (1998)
  * (5) Bell, M.: Future directions in traffic signal control.  Transport. Res. Part A 26, 303–313 (1992)
  * (6) Bendraouche, M., Boudhar, M.: Scheduling jobs on identical machines with agreement graph.  Computers & OR 39(2), 382–390 (2012)
  * (7) Blazewicz, J., Lenstra, J.K., Kan, A.H.G.R.: Scheduling subject to resource constraints: classification and complexity.  Discret. Appl. Math. 5(1), 11–24 (1983)
  * (8) Bodlaender, H.L., Jansen, K.: On the complexity of scheduling incompatible jobs with unit-times.  In: Mathematical Foundations of Computer Science 1993, 18th International Symposium, MFCS’93, Gdansk, Poland, August 30 - September 3, 1993, Proceedings, pp. 291–300 (1993)
  * (9) Bodlaender, H.L., Jansen, K., Woeginger, G.J.: Scheduling with incompatible jobs.  Discret. Appl. Math. 55(3), 219–232 (1994)
  * (10) Borodin, A., Ivan, I., Ye, Y., Zimny, B.: On sum coloring and sum multi-coloring for restricted families of graphs.  Theor. Comput. Sci. 418, 1–13 (2012)
  * (11) Bullock, D., Hendrickson, C.: Roadway traffic control software.  IEEE Trans. Control Syst. Technol. 2, 255–264 (1994)
  * (12) Dell’Amico, M., Iori, M., Martello, S., Monaci, M.: Heuristic and exact algorithms for the identical parallel machine scheduling problem.  INFORMS J. Comput. 20(3), 333–344 (2008)
  * (13) Dell’Amico, M., Martello, S.: A note on exact algorithms for the identical parallel machine scheduling problem.  Eur. J. Oper. Res. 160(2), 576–578 (2005)
  * (14) Donnea, D.D., Furinib, F., Malagutic, E., Calvo, R.W.: A branch-and-price algorithm for the minimum sum coloring problem.  Discrete Applied Mathematics (2020).  DOI 10.1016/j.dam.2020.08.031
  * (15) Duh, R., Fürer, M.: Approximation of _k_ -set cover by semi-local optimization.  In: F.T. Leighton, P.W. Shor (eds.) Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pp. 256–264. ACM (1997)
  * (16) Even, G., Halldórsson, M.M., Kaplan, L., Ron, D.: Scheduling with conflicts: online and offline algorithms.  J. Scheduling 12(2), 199–224 (2009)
  * (17) Furini, F., Malaguti, E., Martin, S., Ternier, I.: ILP models and column generation for the minimum sum coloring problem.  Electron. Notes Discret. Math. 64, 215–224 (2018)
  * (18) Gandhi, R., Halldórsson, M.M., Kortsarz, G., Shachnai, H.: Improved bounds for scheduling conflicting jobs with minsum criteria.  ACM Trans. Algorithms 4(1), 11:1–11:20 (2008)
  * (19) Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness.  W. H. Freeman and Company (1979)
  * (20) Garey, M.R., Graham, R.L.: Bounds for multiprocessor scheduling with resource constraints.  SIAM J. Comput. 4(2), 187–200 (1975)
  * (21) Giaro, K., Kubale, M., Malafiejski, M., Piwakowski, K.: Dedicated scheduling of biprocessor tasks to minimize mean flow time.  In: R. Wyrzykowski, J.J. Dongarra, M. Paprzycki, J. Wasniewski (eds.) Parallel Processing and Applied Mathematics, 4th International Conference, PPAM 2001 Naleczow, Poland, September 9-12, 2001, Revised Papers, _Lecture Notes in Computer Science_ , vol. 2328, pp. 87–96. Springer (2001)
  * (22) Gonen, M.: Coloring problems on interval graphs and trees.  Ph.D. thesis, School of Computer Science, The Open University, Tel-Aviv (2001)
  * (23) Graham, J.: Bounds for certain multiprocessing anomalies.  Bell System Technical Journal 45, 1563–1581 (1966)
  * (24) Graham, R.L.: Bounds on multiprocessing timing anomalies.  SIAM Journal of Applied Mathematics 17(2), 416–429 (1969)
  * (25) Hà, M.H., Vu, D.M., Zinder, Y., Nguyen, T.T.: On the capacitated scheduling problem with conflict jobs.  In: 11th International Conference on Knowledge and Systems Engineering, KSE 2019, Da Nang, Vietnam, October 24-26, 2019, pp. 1–5. IEEE (2019)
  * (26) Halldórsson, M.M., Kortsarz, G.: Tools for multicoloring with applications to planar graphs and partial k-trees.  J. Algorithms 42(2), 334–366 (2002)
  * (27) Halldórsson, M.M., Kortsarz, G., Proskurowski, A., Salman, R., Shachnai, H., Telle, J.A.: Multicoloring trees.  Inf. Comput. 180(2), 113–129 (2003)
  * (28) Halldórsson, M.M., Kortsarz, G., Shachnai, H.: Sum coloring interval and k-claw free graphs with application to scheduling dependent jobs.  Algorithmica 37(3), 187–209 (2003)
  * (29) Haouari, M., Jemmali, M.: Tight bounds for the identical parallel machine-scheduling problem: Part II.  Int. Trans. Oper. Res. 15(1), 19–34 (2008)
  * (30) Hastad, J.: Clique is hard to approximate within $n^{1-\epsilon}$.  In: 37th Annual Symposium on Foundations of Computer Science, FOCS ’96, Burlington, Vermont, USA, 14-16 October, 1996, pp. 627–636. IEEE Computer Society (1996)
  * (31) Hochbaum, D.S., Shmoys, D.B.: A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach.  SIAM J. Comput. 17(3), 539–551 (1988)
  * (32) Hoogeveen, J.A., van de Velde, S.L., Veltman, B.: Complexity of scheduling multiprocessor tasks with prespecified processor allocations.  Discret. Appl. Math. 55(3), 259–272 (1994)
  * (33) Jansen, K.: The optimum cost chromatic partition problem.  In: G.C. Bongiovanni, D.P. Bovet, G.D. Battista (eds.) Algorithms and Complexity, Third Italian Conference, CIAC ’97, Rome, Italy, March 12-14, 1997, Proceedings, _Lecture Notes in Computer Science_ , vol. 1203, pp. 25–36. Springer (1997)
  * (34) Jansen, K.: The mutual exclusion scheduling problem for permutation and comparability graphs.  Inf. Comput. 180(2), 71–81 (2003)
  * (35) Jin, Y., Hamiez, J., Hao, J.: Algorithms for the minimum sum coloring problem: a review.  Artif. Intell. Rev. 47(3), 367–394 (2017)
  * (36) Kaller, D., Gupta, A., Shermer, T.: The $\chi_{t}$ coloring problem.  In: Symposium on Theoretical Aspects of Computer Science, STACS 95, _Lecture Notes in Computer Science_ , vol. 900. Springer (1995)
  * (37) Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems.  Springer, Berlin, Germany (2004)
  * (38) Kowalczyk, D., Leus, R.: An exact algorithm for parallel machine scheduling with conflicts.  J. Sched. 20(4), 355–372 (2017)
  * (39) Kubicka, E.: The chromatic sum of a graph.  Ph.D. thesis, Western Michigan University (1989)
  * (40) Lonc, Z.: On complexity of some chain and antichain partition problems.  In: Proceedings of the 17th International Workshop, WG ’91, pp. 97–104. Springer-Verlag, London, UK (1992)
  * (41) Malafiejski, M., Giaro, K., Janczewski, R., Kubale, M.: Sum coloring of bipartite graphs with bounded degree.  Algorithmica 40(4), 235–244 (2004)
  * (42) Mallek, A., Bendraouche, M., Boudhar, M.: Scheduling identical jobs on uniform machines with a conflict graph.  Comput. Oper. Res. 111, 357–366 (2019)
  * (43) Manuel Ruiz, Pascal Tournebise, Patrick Panciatici: ROADEF Challenge RTE: Grid operation-based outage maintenance planning.  https://www.roadef.org/challenge/2020/en/sujet.php.  Online; accessed 23 January 2021
  * (44) Marx, D.: Minimum sum multicoloring on the edges of trees: (extended abstract).  In: K. Jansen, R. Solis-Oba (eds.) Approximation and Online Algorithms, First International Workshop, WAOA 2003, Budapest, Hungary, September 16-18, 2003, Revised Papers, _Lecture Notes in Computer Science_ , vol. 2909, pp. 214–226. Springer (2003)
  * (45) Mokotoff, E.: An exact algorithm for the identical parallel machine scheduling problem.  Eur. J. Oper. Res. 152(3), 758–769 (2004)
  * (46) Nicoloso, S., Sarrafzadeh, M., Song, X.: On the sum coloring problem on interval graphs.  Algorithmica 23(2), 109–126 (1999)
  * (47) Sen, A., Deng, H., Guha, S.: On a graph partition problem with application to VLSI layout.  Inf. Process. Lett. 43(2), 87–94 (1992)
  * (48) Software, I.: Ibm ilog cplex optimization studio v12.6.3 (2015)
  * (49) Supowit, K.J.: Finding a maximum planar subset of a set of nets in a channel.  IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 6(1), 93–94 (1987)
  * (50) Vazirani, V.V.: Approximation algorithms.  Springer (2001)
  * (51) Woeginger, G.J.: Exact algorithms for np-hard problems: A survey.  In: M. Jünger, G. Reinelt, G. Rinaldi (eds.) Combinatorial Optimization - Eureka, You Shrink!, Papers Dedicated to Jack Edmonds, 5th International Workshop, Aussois, France, March 5-9, 2001, Revised Papers, _Lecture Notes in Computer Science_ , vol. 2570, pp. 185–208. Springer (2001)
  * (52) Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number.  In: J.M. Kleinberg (ed.) Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pp. 681–690. ACM (2006)