Single Machine Scheduling Problems can be Reduced to the Linear Assignment

Assignment Problem Boris Goldengorin Department of Industrial and Systems Engineering  Russ College of

Engineering and Technology, Ohio University, Athens, OH

machine scheduling problems (with n jobs, arbitrary release and due

dates, processing times, priority factors, preemptions) to the Linear Assignment Problems with Additional Constraints minimizing the following objective functions:
The Total Weighted Completion Time,
The Total Weighted Tardiness.
The additional constraints reflecting an ordering of the job parts such that the final part of every job will contribute to the objective function of SPs.
We present the LAP reductions for SPC and SPT and discuss different branch-and-bound algorithms for solving both problems.

branching rules for solving both problems.
In case of equal

processing times (1|pmtn; pj=p; rj|∑wjCj) we provide a lower and upper bounds with approximation ratios ½ and 3/2, respectively, when n tends to infinity and p=2.

Arbitrary Release Dates, Processing Times, Priorities (Weights), and Preemptions Minimizing

the Total Weighted Processing Time (abbreviated SPC)


The Single Machine Scheduling Problem with Arbitrary Release Dates, Processing Times, Priorities (Weights), Preemptions, and Due Dates Minimizing the Total Weighted Tardiness (abbreviated SPT)

The input data for both problems are integer non-negative numbers leading to a schedule without idle intervals

weighted completion time or total weighted tardiness.



Since both problems

are NP-hard (computationally intractable) we are going to design heuristics and exact algorithms.

problem SPC can be represented as an assignment of np

job parts (each of n jobs has p parts) to np time intervals 1, 2,...,np such that every part of job j is assigned to a time interval not earlier than its release date rj . Only the last (p-th) part of every job j is taken into account in the objective function. The cost of its assignment to time t is equal wj t, and the costs for parts 1, 2,...,p − 1 are all equal to 0. The objective is to mini-mize the total cost over all jobs. Thus, SPC problem is equivalent to the linear assignment problem with additional constraints related to release dates rj and also to the sequence of job parts which requires the last part of a job to be assigned to the latest time interval among the time intervals of all its parts. Moreover, release date constraints can be taken into account in the linear assignment problem using infinite costs for the time intervals to which job parts cannot be assigned. For the example at next page, the assignment problem will have the cost matrix shown at the next page.

wj = 1, 2, 3, rj = 1, 4, 7.

The APL optimal solution provides a value of the objective

function fAPL which is not less than {1/p + 2/(n+1) − 2/[p(n+1)]}fSP, i.e.

it does not include the sequence constraints. To incorporate the

sequence constraints, we set the assignment costs cit to be equal to w[(i−1)/p]+1t not only for the last part of a job (when i mod p = 0) but for all its parts. The corresponding matrix for our example is shown at then next slide.

solution is highlighted with gray color. Now it satisfies all

the constraints of the original SPC problem. Unfortunately, it is not an optimal solution to the SPC problem, because its objective function (OF) is different from OF of the SPC.

slides we are going to present BnB algorithms for solving

the SPT exactly by means of different Branching Rules (BRs).
There are many BRs:
(i) branch by an infeasible final part of a job with the largest contribution to the objective function (OF),
(ii) branch by an infeasible not final part of a job with the largest potential contribution to the OF,
(iii) Branch by tolerance based branching rule.

heuristic for the SPC based on the Weighted Shortest Remaining

Processing Time (WSRPT) rule.

The computational complexity of our heuristic is based on the WSRPT rule which is O(n) on each step of the heuristic. Since there are no idle time intervals the total number of steps is not greater than npmax. The WSRPT heuristic stores in memory at most nwj/ρj ratios. So the heuristic has time complexity of O(n^2pmax) and space complexity of O(n).

i7 machine with 2.50 GHz and 8 GB of memory.

Our heuristic is fast enough to solve problems with the number of jobs n = 1000 and the processing times up pj ∼ 1000 in 10 s. For the greater number of jobs n = 10,000 and pj ∼ 10,000 the algorithm needs about 3 h. Average computation times for randomly generated instances are given in Table 2. The average time is computed on 50 instances.

solutions we take n from set {5, 10, 15, 20,

25} and pj ∈[1, 100]. For each n we randomly generated 50 instances in the way described above. Every instance is solved exactly by CPLEX 12 using the BLP model and by the WSRPT heuristic. Then we compute the minimum, average, and maximum relative error of the heuristic solutions over the 50 instances. The results are presented in Table 3. As it can be seen the WSRPT heuristic finds solutions of high quality and the average error does not exceed 0.08% for any combination of n and pj values. We have not considered large values for n because even for n = 25 half of the instances have not been solved in 30,000 s (about 8 h) by the CPLEX. The 50 generated instances for n = 25 have required more than 360 h (15 days) to be solved exactly. We present the results only for pj ∈[1, 100] because for smaller values of pj the average and maximal error are virtually the same and for greater values the errors are even smaller.

row in the AP cost matrix is corresponding to a

job part.

The order in which the job parts should be processed are fixed by the natural order of rows but can be relaxed such that the final part of every job will be completed after all parts of the same job.

Every column in the AP cost matrix is corresponding to a single time unit interval.

The order of time unit intervals is fixed and represented by natural numbering of columns.

The infeasibility of scheduling a job part to a time interval is indicated by a very large number M, and reflecting the potential contribution to the objective function (the part is not released or cannot be released without creation an idle interval) .

additional constratints

J1/P1

+8
T1 T2 T3

T4 T5 T6 T7

J1/P1 T1
J1/P2 T2
J2/P1 T3
J2/P2 T4
J2/P3 T5
J3/P1 T6
J3/P2 T7

J1/P2
J2/P1
J2/P2
J2/P3
J3/P1
J3/P2

- 10

-8

- 8

- 8

- 10

Objective function= 10 +2+8+10+8
= 38

-2

T1 T2 T3

T4 T5 T6 T7

Objective function= 10 +2+8+10+8 = 38

40

38

(5,5)

(5,5)

40

(7,5)

(7,5)

T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P2 P3 P2 P2

All

The found optimal solution to the AP is not feasible to the SPT since the final part 3 of job 2 is scheduled before its preceding part 2. To exclude these infeasibilites we have 2 options:
To prohibit to schedule part 3 of job 2 at the time interval T5;
To prohibit to schedule part 2 of job 2 at the time interval T6.

function= 38+2 = 40
T1 T2

T3 T4 T5 T6 T7

Objective function= 10 +2+8+10+8 = 38

40

38

(5,5)

(5,5)

40

(7,5)

(7,5)

T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P2 P3 P2 P2

All

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2

T1 T2 T3 T4 T5 T6 T7

J1/P1
J1/P2
J2/P1
J2/P2
J2/P3
J3/P1
J3/P2

T4 T5 T6 T7
P1 P2 P1 P2 P1

P2 P3

T1 T2 T3 T4 T5 T6 T7
P1 P2 P1 P2 P1 P2 P3

J1/P1
J1/P2
J2/P1
J2/P2
J2/P3
J3/P1
J3/P2

T1 T2 T3 T4 T5 T6 T7

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2

Objective function= 38+2 = 40

T1 T2 T3 T4 T5 T6 T7

J1/P1
J1/P2
J2/P1
J2/P2
J2/P3
J3/P1
J3/P2

P2 P1 P2 P1 P2 P3
INF
T1 T2 T3

T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2

Objective function= 38+2 = 40

T1 T2 T3 T4 T5 T6 T7

J1/P1
J1/P2
J2/P1
J2/P2
J2/P3
J3/P1
J3/P2

(6,6)

(6,6)

(7,5)

T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P3 P2 P2 P2

J1/P1
J1/P2
J2/P1
J2/P2
J2/P3
J3/P1

T1 T2 T3 T4 T6 T7

Objective function= 40 + 4 = 44

INF

T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P3 P2 P2 P2

44

(4,6)

(4,6)

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P2 P3 P2

T1 T2 T3 T4 T6 T7

J1/P1
J1/P2
J2/P1
J2/P2
J2/P3
J3/P1

Objective function= 44+ 6 + 2 = 52

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P2 P3 P2

52

T3 T4 T5 T6

T7

Objective function= 10 +2+8+10+8 = 38

T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P2 P3 P2 P2

J1/P1
J1/P2
J2/P1
J2/P2
J2/P3
J3/P1
J3/P2

T1 T2 T3 T4 T5 T6 T7

J1/P1
J1/P2
J2/P1
J2/P2
J3/P1
J3/P2

T1 T2 T3 T4 T6 T7

Objective function= 10 +2+8+10+8 = 38

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P2 P3 P1 P2

(6,6)

(6,6)

INF

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P2 P3 P1 P2

(6,6)
INF
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P2

P3 P1 P2

J1/P1
J1/P2
J2/P1
J2/P2
J3/P1
J3/P2

T1 T2 T3 T4 T6 T7

T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P2 P3 P2 P2

T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P2 P3 P2 P2

46

INF

(4,6)

(4,6)

J1/P1
J1/P2
J2/P1
J2/P2
J3/P1
J3/P2

T1 T2 T3 T4 T6 T7

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P3 P2 P2

Objective function= 46 + 12 = 58

58

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P3 P2 P2

P1 P2 P2 P3 P1 P2
T1 T2 T3 T4

T5 T6 T7
P1 P1 P1 P2 P3 P2 P2

46

INF

(4,6)

(4,6)

58

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P3 P2 P2

40

(5,5)

44

40

(7,5)

All

T1 T2 T3 T4 T5 T6 T7
P1 P2 P1 P2 P1 P2 P3

INF

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2

(6,6)

(6,6)

(7,5)

INF

T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P3 P2 P2 P2

44

(4,6)

(4,6)

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P2 P3 P2

52

T1 T2 T3 T4 T5 T6 T7

J1/P1
J1/P2
J2/P1
J2/P2
J2/P3
J3/P1
J3/P2

T1 T2 T3 T4

T5 T6 T7

J1/P1 T1
J1/P2 T2
J2/P1 T3
J2/P2 T4
J2/P3 T5
J3/P1 T6
J3/P2 T7

J1/P2
J2/P1
J2/P2
J2/P3
J3/P1
J3/P2

Objective function= 10 +4+32+40+8
= 94

T2 T3 T4 T5

T6 T7

96

94

(5,5)

(5,5)

96

(7,5)

(7,5)

T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P2 P3 P2 P2

All

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2

T1 T2 T3 T4 T5 T6 T7

Objective function= 10 +4+32+40+8 = 94

Objective function= 94 + 2 = 96

J1/P1
J1/P2
J2/P1
J2/P2
J2/P3
J3/P1
J3/P2

(7,5)
All
T1 T2 T3 T4 T5 T6 T7
P1 P2 P1 P2

P1 P2 P3

T1 T2 T3 T4 T5 T6 T7
P1 P2 P1 P2 P1 P2 P3

INF

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2

J1/P1
J1/P2
J2/P1
J2/P2
J2/P3
J3/P1
J3/P2

T1 T2 T3 T4 T5 T6 T7

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2

Objective function= 94+2 = 96

T1 T2 T3 T4 T5 T6 T7

J1/P1
J1/P2
J2/P1
J2/P2
J2/P3
J3/P1
J3/P2

(6,6)

(6,6)

P2 P1 P2 P1 P2 P3
INF
T1 T2 T3

T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2

T1 T2 T3 T4 T5 T6 T7

J1/P1
J1/P2
J2/P1
J2/P2
J2/P3
J3/P1
J3/P2

(6,6)

(6,6)

(7,5)

T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P3 P2 P2 P2

J1/P1
J1/P2
J2/P1
J2/P2
J2/P3
J3/P1

T1 T2 T3 T4 T6 T7

Objective function= 96 + 4 = 100

INF

T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P3 P2 P2 P2

100

(4,6)

(4,6)

Objective function= 94+2 = 96

P2 P1 P2 P1 P2 P3
INF
T1 T2 T3

T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2

(6,6)

(6,6)

(7,5)

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P2 P3 P2

INF

T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P3 P2 P2 P2

100

(4,6)

(4,6)

T1 T2 T3 T4 T6 T7

J1/P1
J1/P2
J2/P1
J2/P2
J2/P3
J3/P1

Objective function= 100+ 6 + 2 =108

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P2 P3 P2

108

T3 T4 T5 T6

T7

T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P2 P3 P2 P2

J1/P1
J1/P2
J2/P1
J2/P2
J2/P3
J3/P1
J3/P2

T1 T2 T3 T4 T5 T6 T7

J1/P1
J1/P2
J2/P1
J2/P2
J3/P1
J3/P2

T1 T2 T3 T4 T6 T7

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P2 P3 P1 P2

Objective function= 10 +4+32+40+8 = 94

Objective function= 10 +4+32+40+8 = 94

(6,6)

(6,6)

INF

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P2 P3 P1 P2

T7
P1 P1 P2 P2 P3 P1 P2
J1/P1
J1/P2
J2/P1
J2/P2
J3/P1
J3/P2

T1

T2 T3 T4 T6 T7

T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P2 P3 P2 P2

T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P2 P3 P2 P2

106

INF

(4,6)

(4,6)

J1/P1
J1/P2
J2/P1
J2/P2
J3/P1
J3/P2

T1 T2 T3 T4 T6 T7

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P3 P2 P2

Objective function= 102 + 12 = 114

114

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P3 P2 P2

Objective function= 94 + 8 = 106

P1 P2 P2 P3 P1 P2
T1 T2 T3 T4

T5 T6 T7
P1 P1 P1 P2 P3 P2 P2

106

INF

(4,6)

(4,6)

114

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P3 P2 P2

94

(5,5)

100

94

(7,5)

All

T1 T2 T3 T4 T5 T6 T7
P1 P2 P1 P2 P1 P2 P3

INF

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2

(6,6)

(6,6)

(7,5)

INF

T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P3 P2 P2 P2

100

(4,6)

(4,6)

T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P2 P3 P2

108

T1 T2 T3 T4 T5 T6 T7

J1/P1
J1/P2
J2/P1
J2/P2
J2/P3
J3/P1
J3/P2

single machine scheduling problems to the linear assignment problem with

additional constraints.

The idea of branch-and-bound algorithm with two different branching rules is outlined.

Our future computational experiments will show which of eithe two mentioned or tolerance based branching rules should be used for solving these SPs.

objective functions:
Minimize the maximum lateness (Lj=Cj – dj);
Minimize the

makespan (Cmax);
Minimize the weighted number of tardy jobs;
Minimize the total weighted earliness (note that the earliness penalty is nonincreasing in Cj (Ej=max{dj – Cj, 0}).
Minimize the linear combination of the total weighted earliness and the total weighted tardiness with arbitrary weights.
We will design tolerance based branching rules and bounds with the purpose to reduce the total CPU times compared to the costs based counterparts.

Lower and Upper Bounds for the Preemptive Single Machine Scheduling

Problem with Equal Processing Times. Springer Proceedings in Mathematics & Statistics, Vol. 59, 11–30, 2013.

2. M. Batsyn, B. Goldengorin, P. Sukhov, P. M. Pardalos. Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time. Optimization Methods and Software, 2014, 29(5):955–963.

reduction of the SPC and SPT to the Assignment Problem

(AP) with additional constraints. The additional constraints reflecting an ordering of the job parts such that the final part of every job will contribute to the objective function of SPs.

In this talk we present the AP reductions for SPC and SPT and discuss different branch-and-bound algorithms for solving both problems.

Time).
Rule= wj/ρj.

For t=1 : Job#1 only available

For t=2 : w1/ρ1= 2/1=2, w2/ρ2=8/3 = 2.67.
For t=3: w1/ρ1=2, w2/ρ2 = 8/2 = 4 , w3/ρ3=10/2 = 5.
For t=4: w1/ρ1=2, w2/ρ2 = 4 , w3/ρ3=10/1 = 10.
For t=5: w1/ρ1=2, w2/ρ2 = 4.
For t=6: w1/ρ1=2, w2/ρ2 = 8.
For t=7: w1/ρ1=2.

The Total Weighted Completion time = ∑wjcj = 2 (7) + 8 (6) + 10(4) = 102