# An efficient model for the preemptive single machine scheduling of equal-
length jobs

Artem Fomin111email<EMAIL_ADDRESS>Boris Goldengorin222email:
<EMAIL_ADDRESS><EMAIL_ADDRESS>Department of Discrete
Mathematics, Phystech School of Applied Mathematics and Informatics, Moscow
Institute of Physics and Technology, Institutsky lane 9, Dolgoprudny, Moscow
region, 141700

###### Abstract

We propose a Boolean Linear Programming model for the preemptive single
machine scheduling problem with equal processing times, arbitrary release
dates and weights(priorities) minimizing the total weighted completion time.
Almost always an optimal solution of the Linear Programming relaxation is
integral and can be straightforwardly converted into an optimal schedule. To
deal with the fractional solutions we present two heuristics. Very often our
heuristics find solutions with objective function values equal to the lower
bound found by the Linear Programming relaxation. For the cases when upper
bound returned by our heuristics differs from the lower bound we embed the
bounds into a Branch and Bound algorithm, which solves the problem to
optimality. Exhaustive computational study showed that the algorithm
substantially surpasses state-of-the-art methods.

###### keywords:

scheduling, preemptions, total weighted completion time, equal processing
times, branch and bound

##  1 Introduction

We study the preemptive single machine scheduling problem with the Total
Weighted Completion Time (TWCT) objective function. Based on the three field
notation of [7], this problem is usually denoted as $1|pmtn;p_{j}=p;r_{j}|\sum
w_{j}C_{j}$. The first field shows the number of machines, which is one in our
case. The second indicates the job characteristics: $pmtn$ means that jobs can
be preempted, $p_{j}=p$ indicates that all processing times are equal to $p$,
and $r_{j}$ shows that jobs have arbitrary release times. In the third we
define the objective function to be minimized. Here $w_{j}$ and $C_{j}$ are
the weight and completion time of job $j$ respectively, and $\sum w_{j}C_{j}$
is the total weighted completion time function. According to [5] the problem’s
complexity status is still unknown.

The literature devoted to the exact solution of our problem is rather scarce
and we refer the reader to the recent publications [11] for the equal-length
jobs case and [12] for the general case.

We start our paper by formulating and proving several properties of optimal
schedules. All properties apply to a wide range of objective functions and
most of them are valid for non-equal processing times. Some of the properties
were previously studied in [13] and [1].

Based on our optimal schedule properties we formulate a Boolean Linear
Programming (BLP) model to solve the scheduling problem. Our BLP model proved
itself to be quite applicable, as its LP relaxation almost always returns an
optimal integral solution, which can easily be converted into a feasible
optimal schedule. For the rare cases when an optimal solution to the LP
relaxation is fractional we propose two heuristics. We embed our two
heuristics into the Branch and Bound (BnB) algorithm with the aforementioned
LP relaxation solution as the lower bound to verify the optimality of the
returned heuristic solutions.

We perform an exhaustive computational study to evaluate heuristics’ and exact
BnB algorithm’s performance. Exact algorithms far surpasses previous state-of-
the-art methods ([11]) in both CPU times and size of the solved scheduling
problems. Our two heuristics also show great results, outperforming the
accuracy of the counterpart heuristics [14] and [1].

We also show that our model is flexible and can be used for many different
objective functions used in single machine scheduling, which include, but are
not limited to Weighted Number of Tardy Jobs or Total Weighted Tardiness.
Deadlines and unavailability periods can also easily be incorporated in the
model.

The rest of the paper is organized as follows. Several necessary properties of
optimal schedules are proven in section 2. The BLP model is presented in
section 3. Our heuristics, intuitions behind them and BnB algorithm are
detailed in section 4. Computational study results are summarized in section
5. Section 6 proposes various possible modifications of our BLP model. Section
7 contains concluding remarks and future research directions.

###  1.1 Problem formulation

The problem $1|pmtn;r_{j};p_{j}|\sum w_{j}C_{j}$ can be described as follows.
We are given $n$ jobs that need to be processed. The jobs are processed on a
single machine, which means that at each point in time no more than one job
can be processed. Each job has a release time $r_{j}$, processing time $p_{j}$
and a priority weight $w_{j}$, which are all assumed to be integer. Job $j$
becomes available for processing at the moment $r_{j}$ and must be processed
for the time $p_{j}$. If it is specified that $p_{j}=p$, it means that jobs
have equal processing time $p$. Preemptions of one job in favor of another are
allowed at any time and any number of times. A schedule is called feasible, if
it distributes jobs’ processing in time in a way that does not violate release
times and each job $j$ is processed for exactly $p_{j}$ time. Earliest point
in time, at which the job is completed — processed for $p_{j}$ time — is
called completion time and denoted as $C_{j}$. The objective is to find a
feasible schedule, which minimizes $\sum_{j=1}^{n}w_{j}C_{j}$ — the Total
Weighted Completion Time (TWCT).

##  2 Properties of optimal schedules

In this section we formulate and prove several properties of optimal
schedules. The properties are inherent for more general problem
$1|pmtn;r_{j},p_{j}|F(C_{j})$, where processing times $p_{j}$ may differ and
objective function $F(C_{j})$ is any increasing function of completion times.
The proofs will remain correct for non-decreasing functions as well, but only
if statements are changed from ”Optimal schedules have a property” to ”There
is an optimal schedule with a property”. More on that at the end of the
section. The only property specific to the equal-length jobs setting will show
itself to be extremely powerful in modelling the scheduling problem.

######  Remark.

We will suppose that an optimal solution does not contain idle time intervals.
Because if idle time interval is necessary, then there is a point in time,
before which a set of jobs $A$ is fully processed, but jobs in $J\setminus A$
(where $J$ denotes the set of all given jobs) are not yet available for
processing. Then the problem can be decomposed into two subproblems: the
problem of scheduling jobs in $A$ and the problem of scheduling jobs in
$J\setminus A$. And if an idle time interval is not necessary, then an optimal
schedule obviously will not contain it. Or, if the function is non-decreasing,
_there is_ a schedule, which does not contain idle time.

######  Theorem 1.

In an optimal schedule for the problem $1|pmtn;r_{j},p_{j}|F(C_{j})$
preemptions occur at unit points in time only.

###### Proof.

We will prove the theorem by contradiction. Take an optimal schedule. Assume
there are preemptions at fractional points in time. Choose the earliest such
point in time $t$. Let $\underline{t}=\lfloor t\rfloor$ (greatest integer less
than or equal to $t$) and $\overline{t}=\lceil t\rceil$ (least integer greater
than or equal to $t$). As there is a preemption at point $t$, there are
multiple jobs assigned to be processed in the time interval
$[\,\underline{t},\overline{t}\,]$. Select any two $i$ and $j$ out of them.
Let the fractions of the jobs $i$ and $j$ processed in
$[\,\underline{t},\overline{t}\,]$ be $\lambda_{i}$ and $\lambda_{j}$
respectively. Since $t$ is the earliest fractional preemption point, only
integral parts of jobs $i$ and $j$ were processed before the point
$\underline{t}$, hence, integral parts are left for processing after
$\underline{t}$. Which means that there is at least $1-\lambda_{i}$ processing
of job $i$ and at least $1-\lambda_{j}$ processing of job $j$ done after
$\overline{t}$. Without loss of generality, we will assume that completion
time of job $i$ is less than completion time of job $j$.

Then, we find latest (not necessarily continuous) $\lambda_{j}$ amount of job
$i$’s processing which is done after $\overline{t}$, and swap it with job
$j$’s processing in the $[\,\underline{t},\overline{t}\,]$ interval. Finding
that amount is always possible, because $\lambda_{i}+\lambda_{j}\leq 1$, since
they fit in a unit time interval $[\,\underline{t},\overline{t}\,]$.
Therefore, $\lambda_{j}\leq 1-\lambda_{i}$. And there is at least
$1-\lambda_{i}$ of job $i$’s processing after $\overline{t}$, hence, at least
$\lambda_{j}$. And swapping is possible, because $r_{i}$ is integer, therefore
$r_{i}\leq t\Rightarrow r_{i}\leq\underline{t}$.

That swap does not affect job $j$’s completion time, because the parts swapped
are strictly prior to it. And job $i$’s completion time is now earlier,
because its latest processing intervals have been swapped to an earlier time.
Which means that we have found a solution with a lesser objective function
value than the optimal schedule has. Which brings us to contradiction. ∎

Now we will separate each job $j$ into $p_{j}$ job-parts
$j.1,j.2,\ldots,j.p_{j}$ and time into time intervals $1,2,\ldots,T$, where
$t$ stands for the time interval $(t-1,t]$ and $T=\sum_{j=1}^{n}p_{j}$ is the
time horizon.

######  Corollary 1.1.

In an optimal schedule for the problem $1|pmtn;r_{j},p_{j}|F(C_{j})$ every
job-part is entirely assigned to one time interval.

###### Proof.

Immediately follows from Theorem 1, because a schedule with preemptions at
unit points in time will be a schedule, in which every job-part is entirely
assigned to one time interval. ∎

This result allows us to reduce the scheduling problem to the problem of
assigning job-parts to time intervals.

######  Definition 1.

In a specific schedule job $i$ intersects job $j$, if there is job $i$’s
processing assigned in-between of some of job $j$’s processing. The in-between
processing is called intersecting.

[Caption]Job $j$ is intersected by job $i$ [Dx=5,
subticks=5]-¿(0,0)(0,0)(22,0) $j$$i$$j$

######  Definition 2.

In a specific schedule jobs $i$ and $j$ are intersecting, if $i$ intersect $j$
and vice versa.

[Caption]Intersecting jobs $i$ and $j$ [Dx=5, subticks=5]-¿(0,0)(0,0)(22,0)
$i$$j$$i$$j$

######  Theorem 2.

In an optimal schedule for the problem $1|pmtn;r_{j},p_{j}|F(C_{j})$ there are
no intersecting jobs.

###### Proof.

We will prove the theorem by contradiction. Assume that there are intersecting
jobs $i$ and $j$ in an optimal schedule. Without loss of generality, we will
assume that the job $i$’s completion time is less than job $j$’s. Then take
some of job $j$’s intersecting processing and swap it with the same amount of
job $i$’s latest processing. Any positive amount of processing will suffice.
The intersecting processing can only be earlier than job $i$’s latest
processing. And it is later than some other job $i$’s processing, hence, later
than $r_{i}$ and such swap is possible. Job $j$’s completion time has not
changed, because it is later than any of job $i$’s processing. But job $i$’s
completion is now earlier, because we moved the latest processing to an
earlier time. Which brings us to a contradiction to the optimality of the
initial schedule. ∎

[Caption]Theorem 2 swap example [Dx=5, subticks=5]-¿(0,0)(0,0)(22,0) $i$$j$

Fig. 3 provides an example of the swap described in Theorem 2, applied to the
intersecting jobs $i$ and $j$ from Fig. 2.

######  Corollary 2.1.

In an optimal schedule for the problem $1|pmtn;r_{j},p_{j}|F(C_{j})$ if job
$i$ is partially processed between processing intervals of job $j$, then job
$i$ is fully processed between these intervals.

###### Proof.

If job $i$ is not fully processed, then either there is some of its processing
before the earlier interval of job $j$ or some of its processing after the
latter. Job $j$ is already intersected by job $i$. And in the first case, the
earlier processing interval of job $j$ would be between processing intervals
of job $i$; in the second case, the latter processing interval of job $j$
would be between processing intervals of job $i$. Either way, job $i$ would
also be intersected by job $i$, which is impossible by Theorem 2. ∎

[Caption]Cor. 2.1 example [Dx=5, subticks=5]-¿(0,0)(0,0)(22,0)
$i_{1}$$j_{1}$$i_{0}$$j_{2}$$i_{2}$

To clarify, consider an example shown in Fig. 4. $j_{1}$ is the earlier
interval of job $j$, $j_{2}$ is the latter. $i_{0}$ is the part of job $i$,
processed between intervals $j_{1}$ and $j_{2}$. $i_{1}$ and $i_{2}$ depict
two possibilities: either there is some processing interval $i_{1}$ of job $i$
before the $j_{1}$ or some processing interval $i_{2}$ after $j_{2}$. It can
easily be seen that both possibilities make jobs $i$ and $j$ intersecting.

Moving on to our special case with equal processing times, there is a peculiar
property, which does not apply to the general case.

######  Corollary 2.2.

In an optimal schedule for the problem $1|pmtn;r_{j},p_{j}=p|F(C_{j})$ there
are either 0, $p$, or a multiple of $p$ time intervals between the two time
intervals to which one job’s subsequent job-parts are assigned.

###### Proof.

There are zero time intervals between two subsequent job-parts, if the job is
not interrupted at that moment. If it is interrupted, then any jobs, which are
processed in-between, are processed fully before the interrupted job is
continued by Corollary 2.1. To be fully processed, each one of them requires
$p$ time intervals. That is, $p$ time intervals, if there is only one job, or
a multiple of $p$, if several. ∎

For non-decreasing objective functions of completion times from these proofs
immediately follows that _there is_ an optimal schedule with these properties.
The schedule created by swaps in the theorems may not be better than the
starting optimal one, therefore, not contradicting its optimality. It is not
strictly better, but still not worse. Hence, also optimal. Which means that we
can not claim that all optimal schedules have that property, but there is at
least one optimal solution, which has. And finding that solution means solving
the problem. Therefore, a problem with non-decreasing objective function of
completion times can also be reduced to the problem of assigning job-parts to
time intervals.

##  3 BLP model

Now, using theoretical insights described in previous section, we will
formulate a Boolean Linear Programming (BLP) model of the
$1|pmtn;p_{j}=p;r_{j}|\sum w_{j}C_{j}$ problem. The formulation was also
heavily inspired by [2] and previously described in [4].

First, we introduce the indices, the decision variables and define other
necessary objects.

$T=np$ | Time horizon.
---|---
$j\in\\{1,2,\ldots,n\\}$ | Job index.
$k\in\\{1,2,\ldots,p\\}$ | Job part index.
$t\in\\{1,2,\ldots,T\\}$ | Time interval index.
$a\in\\{1,2,\ldots,n\\}$ | Index for subsets of time intervals of jobs.
$b\in\\{1,2,\ldots,p\\}$ | Index for subsets of time intervals of job parts.

Decision variables:

$x_{jkt}=\left\\{\begin{array}[]{ll}1&\mbox{if job $j$'s $k$-th part is
assigned to time interval $t$},\\\ 0&\mbox{otherwise}.\end{array}\right.$

The weights for parts $1,\ldots,p-1$ are given by

$w_{jkt}=\left\\{\begin{array}[]{ll}0&\mbox{for
all}\>\>j\>\mbox{and}\>\>r_{j}+k-1\leq t\leq T-p+k,\\\
\infty&\mbox{otherwise}.\end{array}\right.$

and for part $p$ by

$w_{jpt}=\left\\{\begin{array}[]{ll}w_{j}t&\mbox{for
all}\>\>j\>\mbox{and}\>\>r_{j}+p\leq t,\\\
\infty&\mbox{otherwise}.\end{array}\right.$

Now define a subset of time intervals, which will allow us to make use of
Corollary 2.2:

$\mathcal{T}_{ab}=\left\\{\begin{array}[]{ll}\emptyset&\mbox{if}\>\>b=p\>\>\mbox{and}\>\>a=n,\\\
\\{b,b+p,b+2p,\ldots,b+(a-1)p\\}&\mbox{otherwise.}\end{array}\right.$

The BLP model is formulated as follows:

$\displaystyle\min$
$\displaystyle\sum_{j=1}^{n}\sum_{k=1}^{p}\sum_{t=1}^{T}w_{jkt}x_{jkt}$
$\displaystyle\mbox{subject to}\>\>\quad\sum_{t=1}^{T}x_{jkt}$
$\displaystyle=$ $\displaystyle 1\quad\quad j=1,\ldots,n,\>\>k=1,\ldots,p,$
(1) $\displaystyle\sum_{j=1}^{n}\sum_{k=1}^{p}x_{jkt}$ $\displaystyle=$
$\displaystyle 1\quad\quad t=1,\ldots,T,$ (2)
$\displaystyle\sum_{t\in\mathcal{T}_{ab}}x_{jkt}-\sum_{t\in\mathcal{T}_{ab}}x_{j,k+1,t+1}$
$\displaystyle\geq$ $\displaystyle 0\quad\quad
j=1,\ldots,n,\>\>k=1,\ldots,p-1,$
$\displaystyle\quad\quad\>\>a=1,\ldots,n,\>\>b=1,\ldots,p,$ $\displaystyle
x_{jkt}$ $\displaystyle\in$ $\displaystyle\\{0,1\\}\quad\quad
j=1,\ldots,n,\>\>k=1,\ldots,p,$
$\displaystyle\quad\quad\quad\quad\>\>t=1,\ldots,T.$

Constraints (1) assure that each job part is assigned to exactly one time
interval and constraints (2) state that exactly one job part must be assigned
to each time interval. Constraints (3) state that the job parts have to be
processed in the right order and that the number of time intervals between two
subsequent job parts is either zero or a multiple of $p$. Note that
$\mathcal{T}_{ab}=\emptyset$ when both $b=p$ and $a=n$, since the final time
interval $T$ does not need to be a part of $\mathcal{T}_{ab}$: only the $p$-th
part of a job can be assigned to it. Constraints (4) are Boolean constraints.

| 1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---|---
1.1  | 0 | 0 | 0 | 0 | $\infty$ |  $\infty$
1.2  | $\infty$ | 0 | 0 | 0 | 0 |  $\infty$
1.3  | $\infty$ | $\infty$ | 3 | 4 | 5 | 6
2.1  | $\infty$ | $\infty$ | 0 | 0 | $\infty$ |  $\infty$
2.2  | $\infty$ | $\infty$ | $\infty$ | 0 | 0 |  $\infty$
2.3  | $\infty$ | $\infty$ | $\infty$ | $\infty$ | 15 | 18
|  |  |  |  |  |
Table 1: Weight vector representation

For better understanding of the model, consider the following example: $n=2$
jobs with common processing time $p=3$, release times $r_{1}=1$, $r_{2}=3$ and
weights $w_{1}=1$, $w_{2}=3$. The weights $w_{jkt}$ can be represented as a
square matrix with $np$ rows and $np$ columns(Table 1). Each row corresponds
to a job-part and each column corresponds to a time interval. The value of
$w_{jkt}$ can be found in the cell defined by row $j.k$ and column $t$.

In our model the numbering of job-parts is fixed and a job-part $j.k_{2}$ can
not be processed before job part $j.k_{1}$ if $k_{1}<k_{2}$. This ordering
implies that any job $j$’s $k$-th job-part $j.k$ can not be processed before
the time interval $r_{j}+k-1$ and after the time interval $np-k+1$.

In this example, job 2 becomes available for processing only at $r_{2}=3$,
therefore weights $w_{2.1.1}$ and $w_{2.1.2}$ are assigned $\infty$. Then, for
instance, job-part $2.2$ can not be processed before time interval 4, because
the previous part $2.1$ has to be processed beforehand and the earliest it can
happen is $r_{2}=3$. And from the other end, job-part $2.2$ can not be
processed after time interval 5, because the following part $2.3$ can only be
processed after $2.2$ and $2.3$ is processed not later than time interval 6.

Because only the last job-part contributes to the objective function, all
other weights for job-parts $1,\ldots,p-1$ are 0. And for the last job-part
$p$ in column (time interval) $t$ the cost $w_{jpt}=w_{j}t$ of completing job
$j$ at the moment (time interval) $t$.

In programming, sum of every other number in the weight vector can used as
$\infty$. The value should be greater than the optimal objective function
value. Then, in terms of the scheduling problem, that value is great enough to
never be considered and, in a sense, is infinite.

Note that a regular Integer Linear Programming (ILP) model is obtained when
constraints (4) are replaced by

$x_{jkt}\in\mathbb{Z}_{+}$

and the BLP’s Linear Programming (LP) relaxation is obtained when they are
replaced by

$x_{jkt}\geq 0.$

The model has $npT=n^{2}p^{2}$ variables and $np+T+n^{2}p(p-1)=O(n^{2}p^{2})$
constraints. LP models are polynomially solvable, but since its input size
depends on parameter $p$, that model is only pseudo-polynomially solvable in
terms of the original problem. On the other hand, ILP and BLP models are known
to be NP-complete.

##  4 Algorithms

In this section we describe algorithms, which convert an LP solution into a
Boolean one. The algorithms do not guarantee preservation of the objective
function value, hence they are heuristics. In our computational study we will
also involve the WSRPT heuristic ([1]) which is applied to the problem
$1|pmtn;r_{j}|\sum w_{j}C_{j}$ with arbitrary processing times. The WSRPT
heuristic is one of the best known heuristics for the problem
$1|pmtn;r_{j}|\sum w_{j}C_{j}$. Therefore, it will be useful not only in
search of an optimal solution, but also for comparison with our heuristics.

###  4.1 Heuristics’ description

In this subsection we describe variations of heuristics presented in [4] and
[3] as exact algorithms.

Algorithm 1

  1. 1.

Solve LP relaxation, obtaining the solution $x^{\star}$ and the optimal value
$l_{b}$ of objective function, which will serve as a lower bound.

  2. 2.

Determine $J_{I}$ — a set of jobs, for which all related variables in
$x^{\star}$ are integral, and $J_{F}$ – a set of jobs, which have at least one
fractional related variable. (Both sets may be empty)

  3. 3.

Schedule every job in $J_{I}$ as suggested by $x^{\star}$.

  4. 4.

For every job $j$ in $J_{F}$ determine an ”estimated” completion time as the
greatest $t$, for which $x_{jpt}>0$.

  5. 5.

Schedule jobs in $J_{F}$ in the ascending order of their estimated completion
times to the earliest possible time intervals. If several jobs have equal
estimated completion times, choose the one that has the greatest weight. If
there still are several, choose the one with the smallest index.

Algorithm 2

  1. 1.

Solve LP relaxation, obtaining the solution $x^{\star}$ and the optimal value
$l_{b}$ of objective function, which will serve as a lower bound.

  2. 2.

Determine $J_{I}$ — a set of jobs, for which all related variables in
$x^{\star}$ are integral, and $J_{F}$ – a set of jobs, which have at least one
fractional related variable. (Both sets may be empty)

  3. 3.

Schedule every job in $J_{I}$ as suggested by $x^{\star}$.

  4. 4.

Find the smallest $t$, for which there exists a job $j$, not yet scheduled,
such that $x_{jpt}>0$. If there are multiple such jobs, choose the one with
the smallest index. If there are none, then go to step 6.

  5. 5.

If it is possible to schedule job $j$ not later than time $t$, schedule $j$ to
earliest possible time intervals. If not, remove $x_{jpt}$ from consideration.
Return to step 4.

  6. 6.

If there still are unscheduled jobs, taking all $x_{jpt}$ into consideration
again, find the smallest $t$, for which there exists an unscheduled job $j$
such that $x_{jpt}>0$, and schedule job $j$ to the earliest possible time
intervals. Repeat until all jobs are scheduled.

First step of the algorithms is the most computationally expensive. Although
it is hard to express the time necessary for modern industrial solvers to find
a solution to the LP problem with asymptotics, it is at least $\Omega(m^{2})$,
where $m$ is the number of variables in the LP problem. As we have
$n^{2}p^{2}$ variables in our problem, solving LP problem will take at least
$\Omega(n^{4}p^{4})$ time.

Second step checks every variable, of which there are $n^{2}p^{2}$. Third step
can also easily be done with at most $O(n^{2}p^{2})$ operations. For the
algorithm 1, step 4 can be done in $O(nT)$ time; step 5 requires sorting at
most $n$ completion times, which can be done in $O(n\log n)$ time, and
scheduling, which can be done in $O(T)$ time. For the algorithm 2, steps 4, 5
and 6 can be easily done in $O(npT)$ operations with the most straightforward
implementation. Since $T=np$, without step 1 both algorithms can be executed
in $O(n^{2}p^{2})$ time. It is possible to make computation more efficient at
certain steps, but that is not of particular importance, because solving LP
relaxation is much more time consuming, and these improvements will bear
insignificant time gains.

###  4.2 An example

$j$ | 1 | 2 | 3 | 4
---|---|---|---|---
$r_{j}$ | 1 | 4 | 3 | 2
$w_{j}$ | 4 | 9 | 12 | 9
Table 2: Jobs’ characteristics

To clarify, consider an example. The example consists of $n=4$ jobs with
common processing time $p=2$ and release times and weights presented in Table
2. Now, we will go through Algorithms’ steps to see how they work.

Both algorithms start by solving an LP relaxation. Corresponding LP solution
is presented in the Table 3. The lower bound found by the LP relaxation is
$l_{b}=182$.

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
---|---|---|---|---|---|---|---|---
1.1  | 1.0 |  |  |  |  |  |  |
1.2  |  | 0.5 |  |  |  |  |  | 0.5
2.1  |  |  |  |  | 0.5 |  | 0.5 |
2.2  |  |  |  |  |  | 0.5 |  | 0.5
3.1  |  |  | 0.5 | 0.5 |  |  |  |
3.2  |  |  |  | 0.5 | 0.5 |  |  |
4.1  |  | 0.5 |  |  |  | 0.5 |  |
4.2  |  |  | 0.5 |  |  |  | 0.5 |
|  |  |  |  |  |  |  |
Table 3: LP relaxation solution

Next, both algorithms start by distinguishing between integral and fractional
jobs. Then they both schedule integral ones. In this example, there are no
integral jobs and these steps are skipped in both algorithms. Following steps
are different for the algorithms, so we will consider them separately.

First, consider algorithm 1. On step 4 it determines estimated completion time
by finding the latest non-zero variable, associated with the last job part.
These are marked in red in the table. Then it sorts the jobs by these
estimated completion times and by weights, if completion times are equal. That
results in the order of jobs $(3,4,2,1)$. Then, it schedules the jobs in that
order at the earliest possible time intervals. First, job 3 is scheduled at
time intervals 3 and 4. Then job 4 is scheduled at intervals 2 and 5. Then job
2 is scheduled at intervals 6 and 7. And job 1 is left with 1 and 8. The
resulting schedule is $(14334221)$. Objective function for that schedule is
$4\cdot 8+9\cdot 7+12\cdot 4+9\cdot 5=188$, which is more that $l_{b}=182$.
That example shows that Algorithm 1 is a heuristic, rather than an exact
algorithm.

Moving on to Algorithm 2. On step 4, the algorithm finds the smallest $t$, for
which there is a non-zero variable, associated with the last job-part of a yet
unscheduled job. Initially, it’s $t=2$ for $j=1$. The algorithm moves to step
5. It is possible to schedule job 1, hence, it is scheduled to the earliest
possible time intervals — 1 and 2. Then, algorithm returns to step 4 and finds
next smallest $t=3$ and corresponding $j=4$. But it is not possible to
schedule job 4 before time interval 3. Next earliest non-zero completion
variable belongs to job 3 at $t=5$ and it is possible to schedule it before
that time. Therefore, algorithm schedules it to the earliest possible time
intervals 3 and 4. Note that the completion time can be earlier than the
smallest $t$ found. Next smallest $t=6$ for $j=2$ is possible to schedule and
job 2 is scheduled at intervals 5 and 6. There’s only one unscheduled job
left, which also has an associated with last job-part non-zero decision
variable at $t=8$. But even if it didn’t, it would have been scheduled to
intervals 7 and 8 on step 6. The resulting schedule is $(11334422)$ and its
objective function is $4\cdot 2+9\cdot 8+12\cdot 4+9\cdot 6=182$. Which is
equal to the lower bound, hence, the solution is optimal.

The WSRPT heuristic would construct schedule $(14433221)$, which is also
optimal.

###  4.3 Intuitions behind heuristics

Note that the algorithms are different in how they select jobs to schedule,
but similar in how they schedule selected jobs. Both algorithms try to infer
completion times from the solution of the LP relaxation and build a schedule
with such completion times. The idea to somehow infer completion times of the
jobs and then to schedule them by assigning them to earliest possible time
intervals is actually sensible. Because given a set of completion times, we
can easily construct a schedule with such completion times, if that is
possible.

Closely related Deadline Scheduling Problem $1|prmtn;r_{j},p_{j},D_{j}|F$ is
to decide if there is a schedule such that each task can be completely
executed within the interval of its release time and deadline. The algorithm
to check, if a solution for $1|prmtn;r_{j},p_{j},D_{j}|F$ exists, is described
in [10]. It is often referred to as Earliest Deadline First (EDF) algorithm.
Basically, it schedules jobs in order of their deadlines to earliest possible
time intervals. Feasible schedule exists if and only if the EDF algorithm
successfully finishes. And if it exists, it is built by the EDF algorithm.

It is easy to modify algorithm for building a schedule for predetermined
completion times instead of deadlines. We will assign last job-part of each
job to its specified completion time. Then we will use the EDF algorithm with
completion times used as deadlines and processing times less by one on that
partially assigned schedule. It is easy to see that similar result holds true:
a feasible solution for such completion times exists if and only if the
modified EDF algorithm successfully finishes. And if it exists, it is built by
the modified EDF algorithm.

That explains why the previous heuristics might be effective. Because if we
infer completion times correctly, then we can easily build a schedule for them
with the modified EDF algorithm — if at all possible. And the part of
converting estimated completion times to actual schedules is very similar in
both Algorithm 1 and Algorithm 2. But the completion time inference part is
different, allowing the algorithms to compliment each other.

$n$ | $p$ | Instances | WSRPT | Int LP | Alg1 | Alg2 | Mean pmtn | Time, s.
---|---|---|---|---|---|---|---|---
[ column count = 40, late after line= |  |  |  |  |  |  |  |
Table 4: Experimental results Figure 1: WSRPT optimality depending on $n$
Figure 2: Time depending on problem size $np$. Figure 3: Mean number of
preepmtions depending on $n$.

###  4.4 Exact algorithm for $1|pmtn;p_{j}=p;r_{j}|\sum w_{j}C_{j}$

To find an exact solution, firstly, we solve the LP relaxation and obtain
lower bound $l_{b}$ as the objective function optimal value. Secondly, we
construct three feasible solutions using the WSRPT heuristic, Algorithm 1 and
Algorithm 2. If any of them achieves $\lceil l_{b}\rceil$, then we’ve already
solved the problem completely.

If not, then we employ a Branch and Bound algorithm. It selects the largest
fractional $x_{jkt}$ and considers two options: in an optimal BLP solution,
$x_{jkt}$ is either 0 or 1. Options are easy to take into account with LP
model by adding a corresponding constraint. Algorithm 1 and Algorithm 2 will
be executed for the solution of the new LP model, possibly finding better
schedule.

Branching will continue unless optimal objective value of the LP model in the
node is greater or equal than the value of objective function for an already
found feasible schedule.

##  5 Computational experiments

We performed computational experiments to evaluate the exact algorithm’s and
heuristics’ performance. All computations were performed on a PC with
i5-7300HQ processor with 3.5 GHz and 8 GB of RAM. Gurobi solver([8]) was used
for the LP relaxations.

More than a million instances of various sizes were randomly generated to
evaluate the model’s effectiveness and efficiency. For every problem size
release dates were sampled from uniform distribution $U[1,p(n-6)]$ to ensure
that jobs are released throughout the whole time horizon. Instances which
require idle time were skipped, as they can always easily be divided into
several sub-problems. Weights were sampled from uniform distribution
$U[1,30]$, as 30 different priority levels are typically enough to express
differences between jobs.

The results are presented in the Table 4. First column describes the number of
jobs $n$, second — common processing time $p$, third — number of instances
generated and solved, fourth — how many instances have been solved to
optimality by the WSRPT heuristic, fifth — for how many instances the LP
solution found was integral, sixth — how many of the instances have been
solved to optimality by Algorithm 1, seventh — how many of the instances have
been solved to optimality by Algorithm 2, eighth — mean number of preemptions
in the best of the optimal solutions found, lastly, ninth — mean running time
of the whole BnB complex algorithm.

All generated instances and optimal schedules can be found at [benchmark].

The most important observation is that solutions to the LP relaxation are very
often integral. For only 449 out of more than a million instances, which is
less than $0.037\%$, solutions to the LP relaxation were fractional. Integral
solutions to the LP relaxation can easily be converted into feasible schedules
with the same objective function value.

That shows how powerful the property described in Corollary 2.2 is. Because
the constraints (3) based on it, which are the constraints distinguishing the
scheduling problem from Assignment Problem, are restrictive and powerful
enough, that even without Boolean constraints (4) the relaxed model very
rarely deviates from them by producing fractional solutions. That effect has
not been present in testing of other models, where schedule’s feasibility was
expressed differently.

The WSRPT heuristic’s accuracy deteriorates with growth of $n$. Percentage of
optimal schedules produced by the WSRPT heuristic depending on the number of
jobs $n$ can be seen in the Fig. 5. Despite the fact that the heuristic rarely
finds optimal schedules for larger problems, it does find good approximations.
Mean relative optimality gap did not exceed $0.03\%$ for all problem sizes.
For particular instances optimality gap can exceed $5\%$ for small problems
($n\leq 20$). For larger instances ($n\geq 30$) optimality gap did not exceed
$0.7\%$.

It has to be mentioned that the WSRPT heuristic was designed for the general
problem with different processing times. The heuristic was long considered to
be state-of-the-art, but could not be tested on the problems of that size, as
no efficient exact algorithms were known. The WSRPT heuristic performs
especially well on smaller instances. On larger instances it often fails to
find an optimal schedule, but still finds a very tight approximation to it.
That once more confirms the WSRPT heuristic’s effectiveness, especially
considering how simple it is both to understand and to implement and how
computationally efficient it is.

It is harder to measure the effectiveness of Algorithm 1 and Algorithm 2,
because they are only used when the LP solution is not integral, which does
not happen often. Still, it can be seen that they do turn fractional solutions
into feasible schedules, which are frequently optimal.

Except for only three instances, every other instance was solved at the root
of the BnB algorithm, because at least one out of three heuristics found a
solution with the objective function value equal to the LP relaxation optimal
value. Relative optimality gap reached 7% for Algorithm 1 and 3% for Algorithm
2 in smallest instances with $n=10$ and $p=2$. But for larger instances,
excluding instances with $n=10$ and instances with $n=50,p=2$, relative
optimality gap was always less than $0.2\%$ for both Algorithms.

Even though the complexity of every part of the BnB algorithm depends on $np$,
rather than $n$ or $p$ separately, instances with larger $n$ took more time
than problems with the same $np$, but smaller $n$. Fig.6 shows how processing
time depends on $np$. Possible reason behind that could be that for the same
$np$, weight matrix $w_{jkt}$ in the BLP model is denser for problems with
larger $n$, because there are $n$ non-zero rows for each job’s last job-part.
That also makes optimal objective function value larger and forces us to
choose a larger substitute for $\infty$.

Also, we want to describe the number of preemptions in the optimal solutions.
Preemptions are beneficial in scheduling problems, improving the optimal
schedule’s objective function value by $9.21\%$ on average ([9]). In our
problem setting, we consider preemptions to be instant and cost-free, but in
real-life applications that assumption is usually incorrect. Thus, if the BnB
algorithm finds several optimal schedules, it selects a schedule with the
fewest preemptions as the reported schedule. Relation between the mean number
of preemptions in the reported schedule and $n$ is shown in Fig. 7.

It is only natural that the number of preemptions grows with increase in
number of jobs or increase in jobs’ processing times. Natural, if new jobs
appear throughout the whole time horizon, at least, because, as was proven in
[1], a job can only be preempted in favor of another one at the latter’s
release date. And we deliberately chose distribution of release dates to
create more possibilities for preemptions. Otherwise, after the latest release
date scheduling of not yet started jobs would become trivial, because one
would just have to put them in non-decreasing order of $p_{j}^{\prime}/w_{j}$,
where $p_{j}^{\prime}$ is the remaining processing time of job $j$, see e.g.
[13].

In our testing, we reached the problem size of $np=800$. Remember that
computationally hardest step of the heuristics is finding a solution to the LP
relaxation, which has $O(n^{2}p^{2})$ variables and constraints. For $np=800$
we have more than half a million variables and constraints. It becomes time
consuming to solve problems of that size on a standard personal computer. The
computational time complexity of the heuristics without solving the LP
relaxation and without branching, which very rarely occurs, is only
$O(n^{2}p^{2})$. LP problems in general have received a great deal of
attention: there are many industrial solvers, which can be efficiently used on
powerful machines and distributed systems. Therefore solving larger problems
is absolutely possible with more powerful equipment and/or more time.

State-of-the-art results can be found in [11] for the equal processing time
case or in [12] for the case with different processing times. There,
processing time were sampled in $U[1,9]$ and algorithms could not always find
an optimal solution for the instances with more than 10 jobs and could never
find an optimal solution for the instances with more than 20 jobs in 2 hours.
For the cases, where previous algorithms found an optimal solution, our
algorithm takes significantly less time.

##  6 Model flexibility

In this section we will discuss possible modifications to the model. We have
considered one of the simplest formulations of single machine scheduling
problem with common processing times. This approach can be applied to many
other variations of our single machine scheduling problem. However, two
requirements have to be satisfied. First, the objective function must be a
non-decreasing function of completion times. Second, it must be possible to
precompute the objective function values independently for each job and
express it with weights in the BLP model. An example of an objective function
violating the first criterion is the Total Weighted Earliness and other
similar objective functions. An example of an objective function violating the
second criterion is the Maximum Lateness and other similar objective
functions. Nevertheless, there are still a few popular settings, where our
approach is applicable.

  1. 1.

Several other objective functions like Total Weighted Tardiness, Total
Weighted Number of Tardy Jobs.

  2. 2.

Deadlines. If a job must be finished by a certain point in time, we can either
set infinite weight for variables corresponding to post-deadline processing or
add a constraint, forbidding any post-deadline processing.

  3. 3.

Maintenance and unavailability periods. The columns corresponding to such
periods can be omitted and weights in the model changed accordingly to the
time omitted.

And many others, if only they can be expressed in changes to the weights or
additional constraints. The efficiency of the approach for other settings is a
target of future study.

##  7 Conclusion and further research

In this paper we have coined the Boolean Linear Programming model for solving
the scheduling problem $1|pmtn;r_{j},p_{j}=p|\sum w_{j}C_{j}$. We have proven
several important properties of optimal schedules for a wide class of
scheduling problems. These properties justify and are deeply ingrained in our
model.

To find an optimal schedule, we first solve the LP relaxation of the BLP
model. Very often the solution to the LP relaxation is integral, which solves
the problem immediately. If the solution is fractional, we propose two
heuristics, which convert it to a feasible schedule. We embed our heuristics
in the BnB algorithm, which solves the problem to optimality.

Exhaustive computational experiments with up to 350 jobs show model’s
performance. Size of the problems solved substantially exceeds previous state-
of-the-art results ([11], [12]). The model is scalable and can be used for
larger instances with more computational power or time provided. Also, the
model is quite flexible and allows for numerous modifications to suit other
environments.

First direction of future research is proving — or disproving — integrality of
the objective function value of the LP relaxation of the BLP model for the
TWCT objective function. If the integrality claim is correct, then the next
step is to prove — or disprove — that it is possible to convert a fractional
solution to integral one without increase in the objective function value. If
a polynomial or pseudo-polynomial algorithm converting a fractional solution
into a feasible schedule exists, that would establish the scheduling problem’s
complexity status.

Another direction of future research is to test the model’s efficiency for
preemptive single machine scheduling problems with different setting, e.g.,
problems with different objective functions, such as total weighted tardiness
or weighted number of tardy jobs, problems with deadlines, problems with
unavailability periods, just to mention a few.

Lastly, the study of the preemptive nature of the problem is of great
interest. Since in practice preemptions typically are not cost-free it could
be beneficial to minimize their number. Beyond minimization, it would be
interesting to learn more about the ”price of preemptions”, i.e. the
difference between the objective function values of optimal preemptive and
non-preemptive schedules.

## References

  * Batsyn u. a. [2014] Batsyn u. a. 2014 Batsyn, M. ; Goldengorin, B. ; Pardalos, P. M. ; Sukhov, P.:  Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time.  In: _Optimization Methods and Software_ 29 (2014), S. 955–963
  * Batsyn u. a. [2013] Batsyn u. a. 2013 Batsyn, M. ; Goldengorin, B. ; Sukhov, P. ; Pardalos, P. M.:  Lower and Upper Bounds for the Preemptive Single Machine Scheduling Problem with Equal Processing Times.  In: _Springer Proceedings in Mathematics and Statistics_ 59 (2013), S. 11–27
  * Bouma [2009] Bouma 2009 Bouma, H. W.:  _All Minimal and Maximal Open Single Machine Scheduling Problems are Pseudo-Polynomially Solvable. University of Groningen, The Netherlands_ , Diplomarbeit, 2009
  * Bouma und Goldengorin [2010] Bouma und Goldengorin 2010 Bouma, H.W. ; Goldengorin, B.:  Single machine scheduling: The problem $1|pmtn;p_{j}=p;r_{j}|\sum w_{j}T_{j}$ is pseudopolynomially solvable.  In: _Discrete Optimization_ (2010)
  * Brucker und Knust [2006] Brucker und Knust 2006 Brucker, P. ; Knust, S.:  _Complexity results for scheduling problems_.  2006\. –  URL http://www.mathematik.uni-osnabrueck.de/research/OR/class/
  * [6] . a.(2020)[dataset], Fomin und Goldengorin]benchmark [dataset] u. a. 2020 [dataset] ; Fomin, Artem ; Goldengorin, Boris:  Benchmark instances for the preemptive single machine scheduling of equal-length jobs minimizing Total Weighted Completion Time.  In: _Mendeley data_ (2020), 9
  * Graham u. a. [1979] Graham u. a. 1979 Graham, R.L. ; Lawler, E.L. ; Lenstra, J.K. ; Kan, A.H.G.Rinnooy:  Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey.  In: _Annals of Discrete Mathematics_ 5 (1979), S. 287 – 326. –  ISSN 0167-5060
  * Gurobi Optimization [2020] Gurobi Optimization 2020 Gurobi Optimization, LLC:  _Gurobi Optimizer Reference Manual_.  2020\. –  URL http://www.gurobi.com
  * Hendel u. a. [2009] Hendel u. a. 2009 Hendel, Y. ; Runge, N. ; Sourd, F.:  The one-machine just-in-time scheduling problem with preemption.  In: _Discrete Optimization_ 6 (2009), 2, S. 10–22
  * Horn [1974] Horn 1974 Horn, W. A.:  Some simple scheduling algorithms.  In: _Naval Research Logistics_ 21 (1974), S. 177–185
  * Jaramillo und Erkoc [2017] Jaramillo und Erkoc 2017 Jaramillo, F. ; Erkoc, M.:  Minimizing total weighted tardiness and overtime costs for single machine preemptive scheduling.  In: _Computers and Industrial Engineering_ 107 (2017), S. 109 – 119. –  ISSN 0360-8352
  * Jaramillo u. a. [2020] Jaramillo u. a. 2020 Jaramillo, F. ; Keles, B. ; Erkoc, M.:  Modeling single machine preemptive scheduling problems for computational efficiency.  In: _Annals of Operations Research_ 285 (2020), S. 197–222
  * Lazarev und Kvaratskhelia [2010] Lazarev und Kvaratskhelia 2010 Lazarev, A. A. ; Kvaratskhelia, A. G.:  Properties of Optimal Schedules for the Minimization Total Weighted Completion Time in Preemptive Equal-length Job with Release Dates Scheduling Problem on a Single Machine.  In: _Automation and Remote Control_ 71 (2010), S. 2085–2092
  * Zhongjun u. a. [2006] Zhongjun u. a. 2006 Zhongjun, T. ; Ng, C. T. ; Cheng, T. C. E.:  Single Machine Scheduling with Release Dates.  In: _SIAM Journal on Discrete Mathematics_ 15 (2006), S. 165–192