Preemptive Single Machine Scheduling Problems: Modeling by Data Preprocessing��Boris Goldengorin��Discrete Mathematics Department,�MIPT��

Lecture 2 Voronovo 2021

1

Abstract

In this lecture we suggest a unified reduction of single machine scheduling problems with n jobs, arbitrary release and due dates, processing times, priority factors (weights), preemptions to the Linear Assignment Problems with Additional Constraints minimizing the following objective functions:

1. The Total Weighted Completion Time (TWCT),
2. The Total Weighted Tardiness (TWT).

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 TWCT and TWT and outline different branch-and-bound algorithms for solving both problems.

​

​

Lecture 2 Voronovo 2021

2

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; p_j=p; r_j|∑w_jC_j) we provide a lower and upper bounds with approximation ratios ½ and 3/2, respectively, when n tends to infinity and p=2.

Lecture 2 Voronovo 2021

3

Two Single Machine Scheduling Problems

• The Preempted 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

​

​

​

Lecture 2 Voronovo 2021

4

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

Lecture 2 Voronovo 2021

5

​

​

Since both problems are NP-hard (computationally intractable) we are going to design heuristics and exact enumeration type algorithms.

Informal Reduction to the LAP

Lecture 2 Voronovo 2021

6

​

​

A feasible solution of the scheduling problem (SP) 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 r_j . 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 w_j 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, SP problem is equivalent to the linear assignment problem with additional constraints related to release dates r_j 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.

Example 1|pmtn; p_j=p; r_j|∑w_jC_j

n = 3, p = 4, w_j = 1, 2, 3, r_j = 1, 4, 7.

Lecture 2 Voronovo 2021

7

Lower Bound for the 1|pmtn; p_j=p; r_j|∑w_jC_j

Theorem 3 [1] The APL optimal solution provides a value of the objective function f_APL which is not less than {1/p + 2/(n+1) − 2/[p(n+1)]}f_SP, i.e.

​

Lecture 2 Voronovo 2021

8

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 c_it 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.

Lecture 2 Voronovo 2021

9

Another Reduction of SP to the LAP

​

​

​

Lecture 2 Voronovo 2021

10

The optimal assignment problem solution is highlighted with gray color. Now it satisfies all the constraints of the original SP problem. Unfortunately, it is not an optimal solution to the SP problem, because its objective function (OF) is different from the OF of the SP.

LAP based Upper Bound [1]

Theorem 6

Lecture 2 Voronovo 2021

11

Branch and Bound (BnB) Algorithms for the TWT

• In the next slides we are going to present BnB algorithms for solving the TWT exactly by means of different Branching Rules (BRs).
• Here are the 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.

​

​

​

​

​

​

Lecture 2 Voronovo 2021

12

Informal Problem Formulation with p_j=p

Lecture 2 Voronovo 2021

13

Properties of Optimal Schedules, 1

Lecture 2 Voronovo 2021

14

Remark on Optimal Schedules

We will suppose that an optimal schedule does not contain idle time intervals. An idle interval is possible only when all released jobs have been completed and a new job has not yet been released. An optimal schedule will contain an idle time interval only when that idle interval separates the given schedule into two indepen-dent ones.

Lecture 2 Voronovo 2021

15

1|pmtn; r_j , p_j |F (C₁, . . . , C_n) �Properties of Optimal Schedules, 2

Theorem 1. In an optimal schedule for the problem 1|pmtn; r_j , p_j |F (C₁, . . . , C_n) preemptions occur only at unit time points.

​

Corollary 1.1. In an optimal schedule for the problem 1|pmtn; r_j , p_j |F (C₁, . . . , C_n) every job part is entirely assigned to a single time interval.

Lecture 2 Voronovo 2021

16

1|pmtn; r_j , p_j |F (C₁, . . . , C_n) �Intersecting Jobs

Definition 1. Job i intersects job j if there is job i’s processing assigned in-between of some of job j’s processing.

​

​

​

​

Definition 2. Two jobs i and j are called intersecting if i intersects j and vice versa.

​

Lecture 2 Voronovo 2021

17

Intersecting Jobs

Theorem 2. In an optimal schedule for the problem 1|pmtn; r_j , p_j |F (C₁, . . . , C_n) there are no intersecting jobs.

​

Corollary 2.1. In an optimal schedule for the problem 1|pmtn; r_j , p_j |F (C₁, . . . , C_n) if job i has been partially processed between processing intervals of job j then job i has been completely processed between these intervals.

​

Lecture 2 Voronovo 2021

18

Corollary for Equal Processing Times

Corollary 2.2. In an optimal schedule for the problem 1|pmtn; r_j , p_j = p| F (C₁, . . . , C_n) there are either 0, p, or a multiple of p time intervals between the two time intervals to which the subsequent parts of a particular job are assigned.

​

In the following slides we present the Boolean Linear Programming (BLP) model for the case of equal processing times.

Lecture 2 Voronovo 2021

19

1|pmtn; r_j , p_j = p| F (C₁, . . . , C_n) BLP model, 1

Lecture 2 Voronovo 2021

20

BLP model, 2

Lecture 2 Voronovo 2021

21

Heuristics in BnB Algorithms

• We are going to incorporate an efficient heuristic for the SP 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 np_max. The WSRPT heuristic stores in memory at most nw_j/ρ_j ratios. So, the heuristic has time complexity of O(n^2p_max) and space complexity of O(n).

Lecture 2 Voronovo 2021

22

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 p_j ∼ 1000 in 10 s. For the greater number of jobs n = 10,000 and p_j ∼ 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.

Lecture 2 Voronovo 2021

23

CPU times for the WSPRT rule

Lecture 2 Voronovo 2021

24

Quality of the WSRPT rule

To test the quality of heuristic solutions we take n from set {5, 10, 15, 20, 25} and p_j ∈[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 p_j 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 p_j ∈[1, 100] because for smaller values of p_j the average and maximal error are virtually the same and for greater values the errors are even smaller.

Lecture 2 Voronovo 2021

25

Quality of the WSRPT rule

Lecture 2 Voronovo 2021

26

Two Heuristics Based on the relaxed BLP model

Lecture 2 Voronovo 2021

27

Algorithm 2

Lecture 2 Voronovo 2021

28

Exact Branch-and-Bound Algorithm

1. Solve the LP relaxation and obtain a lower bound lb to the unknown optimal value of our problem 1|pmtn; r_j , p_j = p| F (C₁, . . . , C_n).
2. Construct three feasible schedules using the WSRPT heuristic, Algorithms 1 and 2. If any of them achieves ⌈lb⌉, then we’ve already solved the problem completely.
3. Otherwise, branch by the largest fractional variable x_jkt leading to two subproblems with x_jkt = 0 and x_jkt = 1.
4. Add both subrpoblems to the List of Unsolved Subproblems (LUS), solve one of them and update the best current schedule.
5. If the created LUS is empty return an optimal schedule.

Lecture 2 Voronovo 2021

29

Computational Experiments

All computations were performed on a PC with i5-7300HQ processor with 3.5 GHz and 8 GB of RAM. Gurobi solver(Gurobi Optimization (2020)) was used for solving the LP relaxations of our BLP model.

​

More than a million problem instances with the number of jobs n ∈ {10, 350}, processing times p ∈ {2, 20} such that n×p ≤ 800 were randomly generated with the purpose to evaluate the effectiveness and efficiency of all involved algorithms.

​

The purpose of our computational study is to evaluate the quality of WSRPT, Algorithm 1 and 2 as heuristics.

Lecture 2 Voronovo 2021

30

Computational Results, 1

Lecture 2 Voronovo 2021

31

Computational Results, 2

Lecture 2 Voronovo 2021

32

Computational Results, 3

Lecture 2 Voronovo 2021

33

Number of Preemptions depending on n and p

Lecture 2 Voronovo 2021

34

WSRPT heuristic optimality depending on n and p

Lecture 2 Voronovo 2021

35

CPU times depending on np

Lecture 2 Voronovo 2021

36

Mean number of preemptions depending on n and p

Lecture 2 Voronovo 2021

37

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) .

​

Lecture 2 Voronovo 2021

38

Refresh the Hungarian Algorithm (HA) for Linear Assignment Problem

• One of the best algorithms for solving the Linear Assignment Problem is the Hungarian Algorithm
• Tolerances can be used to exclude the most computationally expensive step of the HA, namely, covering all zeros in the reduced matrix by the minimum number of horizontal and/or vertical lines, i.e. application of
• Konig-Egervary Theorem. In any bipartite graph the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.

Lecture 2 Voronovo 2021

39

Enumeration Algorithms for the AP

How to design and improve the Hungarian Algorithm based on the non-trivial upper and lower tolerances

Lecture 2 Voronovo 2021

40

Hungarian Algorithm

1. Reduce rows and columns by its smllest entry (create at least one zero in each row and column, i.e. reduced matrix)

2. Cover all zeros in the reduced matrix by the minimum number k of lines (horizontal and vertical), and apply Konig-Egervary’s theorem

3. If k=n, then output an optimal AP solution, otherwise reduced all uncovered entries by its smallest uncovered entry and return to 2.

Lecture 2 Voronovo 2021

41

Lecture 2 Voronovo 2021

42

Cost matrix for Machineco with row minima

Cost matrix after row minima are subtracted

Lecture 2 Voronovo 2021

43

Cost matrix after column minimum is subtracted

Four lines required; optimal solution is available

Lecture 2 Voronovo 2021

44

Tolerance Based Algorithm for the AP

Lecture 2 Voronovo 2021

45

Tolerance Based Algorithm for the AP

3

3

2

good

bad

Optimal solution to the AP

The Reduction of SPT to the Linear Assignment Problem with 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

The Reduction of SPT to the Linear Assignment Problem with 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

Reduce the Infeasibilities of the AP solution wrt the SPT.

J1/P1

J1/P2

J2/P1

J2/P2

J2/P3

J3/P1

J3/P2

​

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:

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.

Reduce the Infeasibilities of the AP solution wrt the SPT.

J1/P1

J1/P2

J2/P1

J2/P2

J2/P3

J3/P1

J3/P2

​

Objective 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

​

Lecture 2 Voronovo 2021

50

Objective function= 40+4= 44

40

38

(5,5)

(5,5)

44

40

(7,5)

(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

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

​

Lecture 2 Voronovo 2021

51

40

38

(5,5)

(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

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

Lecture 2 Voronovo 2021

52

40

38

(5,5)

(5,5)

All

J1/P1

J1/P2

J2/P1

J2/P2

J2/P3

J3/P1

J3/P2

​

T1 T2 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

Lecture 2 Voronovo 2021

53

40

38

(5,5)

(5,5)

All

Objective function= 38 + 8 = 46

​

(6,6)

(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

Lecture 2 Voronovo 2021

54

38

(5,5)

(6,6)

(6,6)

INF

T1 T2 T3 T4 T5 T6 T7

P1 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