Single Machine Scheduling Problems can be Reduced to the Linear Assignment Problem

1. Single Machine Scheduling Problems can be Reduced to the Linear Assignment Problem Boris Goldengorin Department of Industrial

and Systems Engineering
Russ College of Engineering and Technology,
Ohio University, Athens, OH
1

2. Abstract

In this talk we suggest a unified reduction of single 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:
(a) The Total Weighted Completion Time,
(b) 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.
2

3. Our Results

• We present a family of Branch-and-Bound
Algorithms with different 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.
3

4. Two Single Machine Scheduling Problems

• The Single Machine Scheduling Problem with 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
4

5. An example: schedule 3 jobs to minimize either the total weighted completion time or total weighted tardiness.

j
pj
1
2
2
3
3
2
wj
2
8
10
rj
1
2
dj
1
3
3
3
Since both problems are NP-hard (computationally intractable)
we are going to design heuristics and exact algorithms.
5

6. Informal Reduction to the LAP

A feasible solution of the scheduling 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 minimize 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 in nite 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.
6

7. Example 1|pmtn; pj=p; rj|∑wjCj

n = 3, p = 4, wj = 1, 2, 3, rj = 1, 4, 7.
j
1
2
3
pj
4
4
4
wj
1
2
3
rj
1
4
dj
1
3
7
3
7

8. Lower Bound for the 1|pmtn; pj=p; rj|∑wjCj

Theorem 3 [1] 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.
8

9. LAP Based Upper Bound

• The main drawback of the LAP that 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.
9

10. Another Reduction of SPC to the LAP

The optimal assignment problem solution is highlighted with
gray color. Now it satis es 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.
10

11. LAP based Upper Bound [1]

Theorem 6
11

12. Branch and Bound (BnB) Algorithms for the SPT

• In the next 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.
12

13. Heuristics in BnB Algorithms

• We are going to incorporate an efficient 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).
13

14. WSRPT rule: Computational Study

The computational experiments are performed on Intel
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.
14

15. CPU times for the WSPRT rule

15

16. Quality of the WSRPT rule

To test the quality of heuristic 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 nds 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.
16

17. Quality of the WSRPT rule

17

18. Assumptions used in the Reduction of SPs to the LAP

• Every 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) .
18

19. The Reduction of SPT to the Linear Assignment Problem with additional constratints

T1
T2
T3
T4 T5
T6
T7
J1/P1
0
0
0
0
0
0
M
J1/P2
M
2
4
6
8
10
12
J2/P1
M
0
0
0
0
M
M
J2/P2
M
M
0
0
0
0
M
J2/P3
M
M
M
8
16
24
32
J3/P1
M
M
0
0
0
0
M
J3/P2
M
M
M
10
20
30
40
-8
- 10
T1
J1/P2
T2
J2/P1
T3
J2/P2
T4
J2/P3
T5
J3/P1
T6
J3/P2
T7
+8
- 10
-2
J1/P1
0
0
0
0
0
0
M
0
0
0
0
0
0
M
0 0
0
8
0
0
M
M
0
2
4
6
8
10
M
0
2
4
6
8
0
M 0
2
12
6
8
0
M
0
0
0
0
M
M
M
0
0
0
0
M
M
M 0
0
8
0
M
M
M
M
0
0
0
0
M
M
M
0
0
0
0
M
M M
0
8
0
0
M
M
M
M
0
8
16
24
M
M
M
0
8
16
14
M M
M
0
0
8
6
M
M
0
0
0
0
M
M
M
0
0
0
0
M
M M
0
8
0
0
M
M
M
M
0
10
20
30
M
M
M
0
10
20
20
M M
M
0
2
12
12
-8
-8
Objective function= 10 +2+8+10+8
= 38
19

20. Reduce the Infeasibilities of the AP solution wrt the SPT.

J1/P1
T1 T2
0
0
T3
T4 T5
T6
T7
0
8
0
0
M
0
0
0
8
0
0
M
J1/P2
M
0
2
12
6
8
0
M
0
2
12
6
8
0
J2/P1
M
0
0
8
0
M
M
M
0
0
8
0
M
M
J2/P2
M
M
0
8
0
0
M
M
M
0
8
0
0
M
J2/P3
M
M
M
0
0
8
6
M
M
M
0
M
8
6
J3/P1
M
M
0
8
0
0
M
M
M
0
8
0
0
M
J3/P2
M
M
M
0
2
12
12
M
M
M
0
2
12
12
Objective function= 10 +2+8+10+8 = 38
All
(7,5)
(5,5)
(5,5)
40
38
(7,5)
40
T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P2 P3 P2 P2
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:
1. To prohibit to schedule part 3 of job 2 at the time
interval T5;
2. To prohibit to schedule part 2 of job 2 at the time
interval T6.
20

21. Reduce the Infeasibilities of the AP solution wrt the SPT.

J1/P1
T1 T2
0
0
T3
T4 T5
T6
T7
0
8
0
0
M
0
0
0
8
0
0
M
J1/P2
M
0
2
12
6
8
0
M
0
2
12
6
8
0
J2/P1
M
0
0
8
0
M
M
M
0
0
8
0
M
M
J2/P2
M
M
0
8
0
0
M
M
M
0
8
0
0
M
J2/P3
M
M
M
0
0
8
6
M
M
M
0
M
8
6
J3/P1
M
M
0
8
0
0
M
M
M
0
8
0
0
M
J3/P2
M
M
M
0
2
12
12
M
M
M
0
2
12
12
All
(7,5)
(5,5)
(5,5)
40
38
(7,5)
40
Objective function= 10 +2+8+10+8 = 38
T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P2 P3 P2 P2
T1 T2
0
J1/P1 0
T3
T4 T5
T6
T7
0
8
0
0
M
J1/P2 M
0
2
12
6
8
0
J2/P1 M
0
0
8
0
M
M
J2/P2 M
M
0
8
0
0
M
J2/P3 M
M
M
0
M
6
4
J3/P1 M
M
0
2
0
0
M
J3/P2 M
M
M
0
0
10
10
Objective function= 38+2 = 40
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2
21

22.

T1
T2
T3
T4 T5
T6
T7
0
0
0
12
0
0
M
M
0
2
16
6
8
0
J2/P1 M
0
0
12
0
M
M
J2/P2 M
M
0
12
0
0
M
J2/P3 M
M
M
0
M
2
0
J3/P1 M
M
0
6
0
0
M
J3/P2 M
M
M
0
M
6
6
J1/P1
J1/P2
Objective function= 40+4= 44
T1 T2 T3 T4 T5 T6 T7
P1 P2 P1 P2 P1 P2 P3
T1
T2
T3
T4 T5
T6
T7
J1/P1
0
0
0
8
0
0
M
J1/P2
M
0
2
12
6
8
0
J2/P1
M
0
0
8
0
M
M
J2/P2
M
M
0
8
0
0
M
J2/P3
M
M
M
0
M
6
4
J3/P1
M
M
0
2
0
0
M
J3/P2
M
M
M
0
0
10
10
All
(7,5)
44
(5,5)
(5,5)
40
38
(7,5)
40
T1 T2 T3 T4 T5 T6 T7
P1 P2 P1 P2 P1 P2 P3
Objective function= 38+2 = 40
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2
22

23.

T1
T2
T3
T4 T5
T6
T7
J1/P1
0
0
0
8
0
0
M
J1/P2
M
0
2
12
6
8
0
J2/P1
M
0
0
8
0
M
M
J2/P2
M
M
0
8
0
0
M
J2/P3
M
M
M
0
M
6
4
J3/P1
M
M
0
2
0
0
M
J3/P2
M
M
M
0
M
10
10
All
(5,5)
(5,5)
38
40
Objective function= 38+2 = 40
(7,5)
(7,5)
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2
40
44
T1 T2 T3 T4 T5 T6 T7
P1 P2 P1 P2 P1 P2 P3
(6,6)
(6,6)
44
T1
T2
T3 T4 T6
T7
J1/P1 0
0
0
12
0
M
J1/P2 M
0
2
16
8
T2
J1/P1
T1
0
T3 T4 T6
T7
8
8
14
0
M
0
J1/P2
M
0
2
10
0
0
M
0
0
6
M
M
J2/P1 M
0
0
12
M
M
J2/P1
J2/P2 M
M
0
12
0
M
J2/P2
M
M
0
6
M
M
J2/P3 M
M
M
0
2
0
J2/P3
M
M
M
0
0
6
J3/P1 M
M
0
6
M
M
J3/P1
M
M
0
0
M
M
Objective function= 40 + 4 = 44
T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P3 P2 P2 P2
(4,6)
52
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P2 P3 P2
INF
T1 T2 T3 T4 T5 T6 T7
(4,6)
P1 P1 P2 P3 P2 P1 P2
INF
T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P3 P2 P2 P2
Objective function= 44+ 6 + 2 = 52
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P2 P3 P2
23

24.

T2
T3
T4 T5
T6
T7
J1/P1
T1
0
M
T1 T2 T3 T4 T5
0
0
8
0
J1/P1 0
0
0
8
0
0
J1/P2
M
0
2
12
6
J2/P1
M
0
0
8
J2/P2
M
M
0
J2/P3
M
M
J3/P1
M
J3/P2
M
0
M
8
0
J1/P2 M
0
2
12
6
8
0
0
M
M
J2/P1 M
0
0
8
0
M
M
8
0
0
M
J2/P2 M
M
0
8
0
0
M
M
0
0
8
6
J2/P3 M
M
M
0
0
8
6
M
0
8
0
0
M
J3/P1 M
M
0
8
0
0
M
M
M
0
2
12
12
J3/P2 M
M
M
0
2
12
12
Objective function= 10 +2+8+10+8 = 38
T6
T7
All
(5,5)
(5,5)
38
40
(6,6)
T1 T2 T3 T4 T5 T6 T7
(6,6)
P1 P1 P1 P2 P3 P2 P2
INF
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P2 P3 P1 P2
T1 T2 T3 T4 T6
0
0
8
0
J1/P1 0
T7
M
J1/P2 M
0
2
12
8
0
J2/P1 M
0
0
8
M
M
J2/P2 M
M
0
8
0
M
J3/P1 M
M
0
8
0
M
J3/P2 M
M
M
0
12
12
Objective function= 10 +2+8+10+8 = 38
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P2 P3 P1 P2
24

25.

T1 T2 T3 T4 T6
0
0
8
0
0
M
J1/P2
M
0
2
4
0
0
J2/P1
M
0
0
0
M
M
J2/P2
M
M
0
8
0
M
J3/P1
M
M
0
0
M
M
J3/P2
M
M
M
0
12
12
J1/P1
T7
Objective function= 38 + 8 = 46
All
(5,5)
(5,5)
38
40
T1 T2 T3 T4 T5 T6 T7
(6,6)
(6,6)
P1 P1 P1 P2 P3 P2 P2
46
T1 T2 T3 T4 T6
12
12 20
0
J1/P1 0
M
J1/P2 M
0
12
14
16
0
T7
J2/P1 M
0
0
0
M
M
J2/P2 M
M
0
8
M
M
J3/P1 M
M
0
0
M
M
J3/P2 M
M
M
0
0
0
(4,6)
58
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P3 P2 P2
INF
(4,6)
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P2 P3 P1 P2
INF
T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P2 P3 P2 P2
Objective function= 46 + 12 = 58
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P3 P2 P2
25

26.

T1 T2
0
0
0
8
0
0
M
J1/P2
M
0
2
12
6
8
0
J2/P1
M
0
0
8
0
M
M
J2/P2
M
M
0
8
0
0
M
J2/P3
M
M
M
0
0
8
6
J3/P1
M
M
0
8
0
0
M
J3/P2
M
M
M
0
2
12
12
J1/P1
T3
T4 T5
T6
T7
All
(5,5)
(5,5)
38
40
(7,5)
(7,5)
(6,6)
40
44
T1 T2 T3 T4 T5 T6 T7
P1 P2 P1 P2 P1 P2 P3
46
(6,6)
(6,6)
44
(4,6)
52
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P2 P3 P2
INF
(4,6)
(6,6)
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2
(4,6)
58
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P3 P2 P2
INF
(4,6)
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P2 P3 P1 P2
INF
T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P2 P3 P2 P2
INF
T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P3 P2 P2 P2
26

27. Minimizing the Total Weighted Completion by using Assignment Problem.

T1
T2
T3
T4 T5
T6
T7
J1/P1
0
0
0
0
0
0
M
J1/P2
M
4
6
8
10
12
14
J2/P1
M
0
0
0
0
M
M
J2/P2
M
M
0
0
0
0
M
J2/P3
M
M
M
32
40
48
56
J3/P1
M
M
0
0
0
0
M
J3/P2
M
M
M
40
50
60
70
0
0
0
8
0
0
M
M
0
2
12
6
8
0
M
0
0
8
0
M
M
M
M
0
8
0
0
M
M
M
M
0
0
8
6
M
M
0
8
0
0
M
M
M
M
0
2
12
12
Objective function= 10 +4+32+40+8
= 94
J1/P1
T1
J1/P2
T2
J2/P1
T3
J2/P2
T4
J2/P3
T5
J3/P1
T6
J3/P2
T7
27

28. Converge the Infeasible solution to Feasible solution.

J1/P1
T1 T2
0
0
T3
T4 T5
T6
T7
0
8
0
0
M
0
0
0
8
0
0
M
J1/P2
M
0
2
12
6
8
0
M
0
2
12
6
8
0
J2/P1
M
0
0
8
0
M
M
M
0
0
8
0
M
M
J2/P2
M
M
0
8
0
0
M
M
M
0
8
0
0
M
J2/P3
M
M
M
0
0
8
6
M
M
M
0
M
8
6
J3/P1
M
M
0
8
0
0
M
M
M
0
8
0
0
M
J3/P2
M
M
M
0
2
12
12
M
M
M
0
2
12
12
Objective function= 10 +4+32+40+8 = 94
All
(7,5)
(5,5)
(5,5)
96
94
(7,5)
96
T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P2 P3 P2 P2
J1/P1
J1/P2
J2/P1
J2/P2
T1
0
T2
T3
T6
T7
0
0
8
0
0
M
M
0
2
12
6
8
0
M
0
0
8
0
M
M
M
M
0
8
0
0
M
M
M
M
0
M
6
4
M
M
0
2
0
0
M
M
M
M
0
0
10
10
J2/P3
J3/P1
J3/P2
T4 T5
Objective function= 94 + 2 = 96
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2
28

29.

T4 T5
T6
T7
0
12
0
0
M
0
2
16
6
8
0
J2/P1 M
0
0
12
0
M
M
J2/P2 M
M
0
12
0
0
M
J2/P3 M
M
M
0
M
2
0
J3/P1 M
M
0
6
0
0
M
J3/P2 M
M
M
0
M
6
6
J1/P1
J1/P2
T1
T2
T3
0
0
M
Objective function= 96 + 4 = 100
T1 T2 T3 T4 T5 T6 T7
P1 P2 P1 P2 P1 P2 P3
T1
T2
T3
T4 T5
T6
T7
J1/P1
0
0
0
8
0
0
M
J1/P2
M
0
2
12
6
8
0
J2/P1
M
0
0
8
0
M
M
J2/P2
M
M
0
8
0
0
M
J2/P3
M
M
M
0
M
6
4
J3/P1
M
M
0
2
0
0
M
J3/P2
M
M
M
0
0
10
10
All
(5,5)
(5,5)
96
94
(7,5)
(7,5)
96
100
T1 T2 T3 T4 T5 T6 T7
P1 P2 P1 P2 P1 P2 P3
(6,6)
(6,6)
INF
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
P1 P1 P2 P3 P2 P1 P2
29

30.

T1
T2
T3
T4 T5
T6
T7
J1/P1
0
0
0
8
0
0
M
J1/P2
M
0
2
12
6
8
0
J2/P1
M
0
0
8
0
M
M
J2/P2
M
M
0
8
0
0
M
J2/P3
M
M
M
0
M
6
4
J3/P1
M
M
0
2
0
0
M
J3/P2
M
M
M
0
0
10
10
All
(5,5)
(5,5)
Objective function= 94+2 = 96
(7,5)
(7,5)
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2
94
96
96
100
T1 T2 T3 T4 T5 T6 T7
P1 P2 P1 P2 P1 P2 P3
(6,6)
(6,6)
INF
100
T1
T2
T3 T4 T6
T7
J1/P1 0
0
0
12
0
M
J1/P2 M
0
2
16
8
0
J2/P1 M
0
0
12
M
M
J2/P2 M
M
0
12
0
M
J2/P3 M
M
M
0
2
0
J3/P1 M
M
0
6
M
M
(4,6)
T1 T2 T3 T4 T5 T6 T7
(4,6)
P1 P1 P2 P3 P2 P1 P2
INF
T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P3 P2 P2 P2
Objective function= 96 + 4 = 100
T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P3 P2 P2 P2
30

31.

T2
J1/P1
T1
0
T3 T4 T6
T7
8
8
14
0
M
J1/P2
M
0
2
10
0
0
J2/P1
M
0
0
6
M
M
J2/P2
M
M
0
6
M
M
J2/P3
M
M
M
0
0
6
J3/P1
M
M
0
0
M
M
All
(5,5)
(5,5)
(7,5)
(7,5)
96
100
Objective function= 100+ 6 + 2 =108
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P2 P3 P2
94
96
T1 T2 T3 T4 T5 T6 T7
P1 P2 P1 P2 P1 P2 P3
(6,6)
(6,6)
INF
100
(4,6)
108
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P2 P3 P2
T1 T2 T3 T4 T5 T6 T7
(4,6)
P1 P1 P2 P3 P2 P1 P2
INF
T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P3 P2 P2 P2
31

32.

T2
T3
T4 T5
T6
T7
J1/P1
T1
0
M
T1 T2 T3 T4 T5
0
0
8
0
J1/P1 0
0
0
8
0
0
J1/P2
M
0
2
12
6
J2/P1
M
0
0
8
J2/P2
M
M
0
J2/P3
M
M
J3/P1
M
J3/P2
M
0
M
8
0
J1/P2 M
0
2
12
6
8
0
0
M
M
J2/P1 M
0
0
8
0
M
M
8
0
0
M
J2/P2 M
M
0
8
0
0
M
M
0
0
8
6
J2/P3 M
M
M
0
0
8
6
M
0
8
0
0
M
J3/P1 M
M
0
8
0
0
M
M
M
0
2
12
12
J3/P2 M
M
M
0
2
12
12
Objective function= 10 +4+32+40+8 = 94
T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P2 P3 P2 P2
T6
T7
All
(5,5)
(5,5)
94
96
(6,6)
(6,6)
INF
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P2 P3 P1 P2
T1 T2 T3 T4 T6
0
0
8
0
J1/P1 0
T7
M
J1/P2 M
0
2
12
8
0
J2/P1 M
0
0
8
M
M
J2/P2 M
M
0
8
0
M
J3/P1 M
M
0
8
0
M
J3/P2 M
M
M
0
12
12
Objective function= 10 +4+32+40+8 = 94
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P2 P3 P1 P2
32

33.

T1 T2 T3 T4 T6
0
0
8
0
0
M
J1/P2
M
0
2
4
0
0
J2/P1
M
0
0
0
M
M
J2/P2
M
M
0
8
0
M
J3/P1
M
M
0
0
M
M
J3/P2
M
M
M
0
12
12
J1/P1
T7
Objective function= 94 + 8 = 106
All
(5,5)
(5,5)
94
96
T1 T2 T3 T4 T5 T6 T7
(6,6)
(6,6)
P1 P1 P1 P2 P3 P2 P2
T1
J1/P1 0
T2
T3
T4 T6
12
12
20
0
M
J1/P2 M
12
14
16
0
0
J2/P1 M
0
0
0
M
M
J2/P2 M
M
0
8
M
M
J3/P1 M
M
0
0
M
M
J3/P2 M
M
M
0
0
0
INF
106
T7
(4,6)
114
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P3 P2 P2
(4,6)
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P2 P3 P1 P2
INF
T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P2 P3 P2 P2
Objective function= 102 + 12 = 114
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P3 P2 P2
33

34.

T1 T2
0
0
0
8
0
0
M
J1/P2
M
0
2
12
6
8
0
J2/P1
M
0
0
8
0
M
M
J2/P2
M
M
0
8
0
0
M
J2/P3
M
M
M
0
0
8
6
J3/P1
M
M
0
8
0
0
M
J3/P2
M
M
M
0
2
12
12
J1/P1
T3
T4 T5
T6
T7
All
(5,5)
(5,5)
94
94
(7,5)
(7,5)
(6,6)
94
100
T1 T2 T3 T4 T5 T6 T7
P1 P2 P1 P2 P1 P2 P3
108
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P2 P3 P2
INF
106
(6,6)
(6,6)
INF
100
(4,6)
(6,6)
(4,6)
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P3 P2 P1 P2
(4,6)
114
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P1 P3 P2 P2
(4,6)
T1 T2 T3 T4 T5 T6 T7
P1 P1 P2 P2 P3 P1 P2
INF
T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P2 P3 P2 P2
INF
T1 T2 T3 T4 T5 T6 T7
P1 P1 P1 P3 P2 P2 P2
34

35. Summary

• In this talk we have presented the reduction of two 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.
35

36. Future Research Directions

• We will extend our approach to the following 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.
36

37. References

• 1. M. Batsyn, B. Goldengorin, P. Sukhov, P. M. Pardalos. 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.
37

38. Questions?

38

39. Thank you!

39

40. Old abstract

• Recently Batsyn et al. (2013, 2014) have
suggested a 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.
40

41.

41

42. Weighted Shortest Remaining Processing Time Heuristic

J1
J2
J3
j
1
2
3
3
2
2
1
Time
1
2
3
4
5
6
7
Dj
J1
Release Time
J2,J3
Rule= (Priority Factor/ Remaining processing 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
42