Chapter 9: Interval Scheduling, Reservations, and Timetabling Phan Nguyen Ky Phuc December 15, 2021 Contents

1	Reservation with Slack	2
	1.1	Heuristic Algorithm ............................................................................	2
	1.2	Example ....................................................................................................................	3
		1.2.1	Iteration 0 ...............................................................................	3
		1.2.2	Job 7 .............................................................................................................	4
		1.2.3	Job 6 .............................................................................................................	5
		1.2.4	Job 1 .............................................................................................................	5
		1.2.5	Job 4 .............................................................................................................	5
		1.2.6	Job 5 .............................................................................................................	6
	1.3	Multiple Machines .............................................................................	6
	1.4		Job 3 ..............................................................................................................	7
	1.5		Job 4 ..............................................................................................................	8
	1.6		Job 1 ..............................................................................................................	8
	1.7		Job 2 ..............................................................................................................	8
2	Timetabling with Operator or Tooling Constraints	9
	2.1	Example ....................................................................................................................	9
		2.1.1	Algorithm Application ...............................................................	10
		2.1.2	Step 1 ...........................................................................................................	10

2.1.3 Step 2 ......................................................................................... 10 2.1.4 Step 3 ......................................................................................... 11 2.1.5 Step 4 ......................................................................................... 11 2.1.6 Final Schedule.............................................................................. 11 3 Assignment 11 1 Reservation with Slack 1.1 Heuristic Algorithm

• Let _?it denote the number of activities that may be assigned to resource i during interval [t - 1,t].
• This factor thus corresponds to a potential utilization of resource i in time slot t. The higher this number is, the more flexible resource i is in this time slot.
• A second factor is the number of resources to which activity j can be assigned, i.e., the number of resources in set Mj, which is denoted by | Mj |. The larger this number, the more flexible activity j is.
• Define for activity j a priority index Ij that is a function of _wj/pj and | Mj |, i.e., I_j = f (wj/pj, | Mj |)
• The activities can now be ordered in increasing order of their indices, i.e., I1 = I2 = ... = I_n
• If the activity needs a resource over the period [t, t + pj], then the selection of resource i depends on a function of the factors ?i,t+1, ..., ?i,t+pji.e., g(?i,t+1, ..., ?i,t+pj). For example,

g(?i,t+1, ..., ?i,t+pj) =

~ pj l=1

?i,t+l) /pj

g(?i,t+1, ..., ?i,t+pj)= ^max ~?i,t+1, ..., ?i,t+pj Algorithm 1 Maximizing Weighted Number of Activities Input: Given job parameters pj, wj, rj, dj, Mj Process:

1. Step 1
2. Set j=1
4. Step 2
5. Take activity j and select, among the resources and time slots available, the resource and time slots with the lowest _g(?i,t+1, ..., _?i,t+pj) rank. Discard activity j if it cannot be assigned to any machine at any time.
7. Step 3
8. If j = n STOP, otherwise set j = j + 1 and return to Step 2.

Activities	1	2	3	4	5	6	7
pj	3	10	9	4	6	5	3
wj	2	3	3	2	1	2	3
rj	5	0	2	3	2	4	5
dj	12	10	20	15	18	19	14
Mj	{1,3}	{1,2}	{1,2,3}	{2,3}	{1}	{1}	{1,2}

1.2 Example 1.2.1 Iteration 0 The index function is given by | Mj | Ij = (wj/pj) The indices for the activities are given by The potential usage of for resource 1,2 and 3 are given through Table 1: The activity indices Ii

Activities	1	2	3	4	5	6	7
Ij	3	6.67	9	4	6	2.5	2

Now assume that the job is assigned to the slot according to g(?i,t+1, ..., ?i,t+pj) = max~?i,t+1, ..., ?i,t+pj ~ According to the index Ij calculated above, the job 7 is scheduled first. Ho Chi Minh City International University Scheduling Industrial Systems Engineering Department Lecturer: Phan Nguyen Ky Phuc Table 2: Potential Usage of Resource 1

Time	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
Job 1	0	0	0	0	0	1	1	1	1	1	1	1	0	0	0	0	0	0	0	0
Job 2	1	1	1	1	1	1	1	1	1	1	0	0	0	0	0	0	0	0	0	0
Job 3	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
Job 4	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Job 5	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0	0
Job 6	0	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0
Job 7	0	0	0	0	0	1	1	1	1	1	1	1	1	1	0	0	0	0	0	0
Resource 1	1	1	3	3	4	6	6	6	6	6	5	5	4	4	3	3	3	3	2	1

Table 3: Potential Usage of Resource 2

Time	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
Job 1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Job 2	1	1	1	1	1	1	1	1	1	1	0	0	0	0	0	0	0	0	0	0
Job 3	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
Job 4	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	0	0	0	0	0
Job 5	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Job 6	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Job 7	0	0	0	0	0	1	1	1	1	1	1	1	1	1	0	0	0	0	0	0
Resource 2	1	1	2	3	3	4	4	4	4	4	3	3	3	3	2	1	1	1	1	1

Table 4: Potential Usage of Resource 3

Time	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
Job 1	0	0	0	0	0	1	1	1	1	1	1	1	0	0	0	0	0	0	0	0
Job 2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Job 3	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
Job 4	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	0	0	0	0	0
Job 5	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Job 6	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Job 7	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
Resource 3	0	0	1	2	2	3	3	3	3	3	3	3	2	2	2	1	1	1	1	1

Table 5: Summary of Potential Usage of 3 Resources

Time	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
Resource 1	1	1	3	3	4	6	6	6	6	6	5	5	4	4	3	3	3	3	2	1
Resource 2	1	1	2	3	3	4	4	4	4	4	3	3	3	3	2	1	1	1	1	1
Resource 3	0	0	1	2	2	3	3	3	3	3	3	3	2	2	2	1	1	1	1	1

1.2.2 Job 7 Since the p7 = 3 the value of g7,5 = (u7,5 + _u7,6 + _u7,7) /3 Job 7 is scheduled from 11 -+ 14 Ho Chi Minh City International University Scheduling Industrial Systems Engineering Department Lecturer: Phan Nguyen Ky Phuc Table 6: Calculate g for job 7

Time	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
Res 1	1	1	3	3	4	6	6	6	6	6	5	5	4	4	3	3	3	3	2	1
Res 2	1	1	2	3	3	4	4	4	4	4	3	3	3	3	2	1	1	1	1	1
Res 3	0	0	1	2	2	3	3	3	3	3	3	3	2	2	2	1	1	1	1	1
J7,g1,t	0	0	0	0	0	6	6	6	5.7	5.3	4.7	4.3	0	0	0	0	0	0	0	0
J7,g2,t	0	0	0	0	0	4	4	4	3.7	3.3	3.0	3.0	0	0	0	0	0	0	0	0

Update the Resource Usage and order job 6 1.2.3 Job 6 Table 7: Calculate g for job 6

Time	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
Res 1	1	1	3	3	4	5	5	5	5	5	4				3	3	3	3	2	1
Res 2	1	1	2	3	3	3	3	3	3	3	2				2	1	1	1	1	1
Res 3	0	0	1	2	2	3	3	3	3	3	3	3	2	2	2	1	1	1	1	1
J6, g1,t	0	0	0	0	4.8	5	4.8								2.8

Job 6 is scheduled from 14 -+ 19 Update the Resource Usage and order job 1 1.2.4 Job 1 Table 8: Calculate g for job 1

Time	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
Res 1	1	1	3	3	4	4	4	4	4	4	3									1
Res 2	1	1	2	3	3	3	3	3	3	3	2				2	1	1	1	1	1
Res 3	0	0	1	2	2	3	3	3	3	3	3	3	2	2	2	1	1	1	1	1
J1,g1,t						4	4	4	3.7
J1,g3,t						3	3	3	3

Job 1 is scheduled from 8 -+ 10 Update the Resource Usage and order job 4 1.2.5 Job 4 Job 4 is scheduled from 3 -+ 6 Update the Resource Usage and order job 5 Table 9: Calculate g for job 4

Time	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
Res 1	1	1	3	3	3	3	3	3												1
Res 2	1	1	2	3	3	3	3	3	3	3	2				2	1	1	1	1	1
Res 3	0	0	1	2	2	2	2	2				3	2	2	2	1	1	1	1	1
J4,g2,t				3	3								0	0	0	0	0	0	0	0
J4,g3,t				2	2

1.2.6 Job 5 Table 10: Calculate g for job 5

Time	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
Res 1	1	1	3	3	3	3	3	3												1
Res 2	1	1	2					2	2	2	1				1	1	1	1	1	1
Res 3	0	0	1					1				2	1	1	1	1	1	1	1	1
J5,g1,t			3

Job 5 is scheduled from 2 -+ 7 Update the Resource Usage Table 11: The resource usage after job 5 is assigned

Time	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
Res 1	1	1																		1
Res 2	1	1	2					2	2	2	1				1	1	1	1	1	1
Res 3	0	0	1					1				2	1	1	1	1	1	1	1	1

It is impossible to schedule the rest job. We stop here 1.3 Multiple Machines The algorithm above can be extended to the case where number of each time of machine is greater than 1 The number of machine type 1 and 2 are 2 Calculate the index priority of each job (>K ~ mjk pj k=1 Nk Ij = _____________ where: mjk : be the number of resource type k which is required by job j Table 12: The data of example 2

Job	1	2	3	4
wj	3	2	2	1
pj	2	3	1	1
rj	0	2	1	2
dj	5	7	6	6
Machine 1	2	0	1	1
Machine 2	1	2	0	1

Nk : be the maximum number of resource type k I1 = (2/2 + 1/2) 2 3 Table 13: The priority index

Job	1	2	3	4
Ij	1	1.5	0.25	1

Table 14: Summary of usage resource

Time	0	1	2	3	4	5	6
M1	2	3	4	4	4	2	0
M2	1	1	4	4	4	3	2
RemainM1	2	2	2	2	2	2	2
RemainM2	2	2	2	2	2	2	2

1.4 Job 3 Table 15: Summary of usage resource of Job 3

Time	0	1	2	3	4	5	6
M1	2	3	4	4	4	2	0
M2	1	1	4	4	4	3	2
Remain M1	2	2	2	2	2	2	2
Remain M2	2	2	2	2	2	2	2
J3,M1 usage		1.5	2	2	2	1

Job 3 is assigned to time slot 5 Chapter 09 Page 7 1.5 Job 4 Then resource is updated Assume that job 4 is selected next Table 16: Summary of usage resource of Job 4

Time	0	1	2	3	4	5	6
M1	2	2	3	3	3	1	0
M2	1	1	4	4	4	3	2
RemainM1	2	2	2	2	2	1	2
RemainM2	2	2	2	2	2	2	2
J4, M1 usage			1.5	1.5	1.5	1
J4, M2 usage			2	2	2	2
Total			3.5	3.5	3.5	2.5

Job 4 is assigned to slot 5. 1.6 Job 1 Table 17: Summary of usage resource of Job 1

Time	0	1	2	3	4	5	6
M1	2	2	2	2	2	0	0
M2	1	1	3	3	3	2	2
Remain M1	2	2	2	2	2	0	2
Remain M2	2	2	2	2	2	1	2
J1, M1 usage	2	2	2	2
J1, M2 usage	0.5	0.5	1.5	1.5
Total	2.5	2.5	3.5	3.5

Job 1 is assigned to slot 0 1.7 Job 2 Table 18: Summary of usage resource of Job 2

Time	0	1	2	3	4	5	6
M1	0	0	0	0	0	0	0
M2	0	2	2	2	2	2	2
RemainM1	0	0	2	2	2	0	2
RemainM2	1	1	2	2	2	1	2
J2, M2 Usage			2
Total			2

Job 2 is assigned to slot 2 Chapter 09 Page 8 2 Timetabling with Operator or Tooling Constraints Algorithm 2 Graph Coloring Heuristic Input: Given job parameters pj, wj, rj, dj, Mj Process:

1. Step 1
2. Arrange the nodes in decreasing order of their degree.
4. Step 2
5. Color a node of maximal degree with Color 1.
7. Step 3
8. Choose an uncolored node with maximal saturation level.
9. If there is a tie, choose any one of the nodes with maximal degree in the uncolored subgraph.
11. Step 4
12. Color the selected node with the color with the lowest possible number.
14. Step 5
15. If all nodes are colored, STOP. Otherwise go to Step 3..

• The degree of a node is the number of arcs connected to a node;
• The saturation level of a node in a partially colored graph, is the number of differently colored nodes already connected to it. In the coloring process, the first color to be used is labeled Color 1, the second Color 2, and so on.

2.1 Example Gary, Hamilton, Izak and Reha are university professors attending a national conference. During this conference seven one hour meetings have to be scheduled in such a way that each one of the four professors can be present at all the meetings he has to attend. The goal is to schedule all seven meetings in a single afternoon between 2 p.m. and 6 p.m.

Activities	1	2	3	4	5	6	7
Gary,	1	0	0	1	1	0	1
Hamilton	1	1	1	0	0	0	0
Izak	0	0	1	0	1	1	0
Reha	1	0	1	1	1	0	0

2.1.1 Algorithm Application In this table, if activity i and j have the common resource, then there is an arc between node i and node j The degree of each node is Figure 1: Example of Graph Coloring Algorithm Table 19: Node Degree

Node	1	2	3	4	5	6	7
Degree	5	2	5	4	5	2	3

2.1.2 Step 1 Among node 1, 3, and 5 choose an arbitrarily node. For example, node 1 is selected. Coloring node 1 with Color 1, then update the staturation and degree of other node Table 20: Node Degree and Saturation

Node	1 (Color 1)	2	3	4	5	6	7
Saturation	_	1	1	1	1	0	1
Degree	_	1	4	3	4	2	2

2.1.3 Step 2 Among node 3, and 5 choose an arbitrarily node. Node 3 is selected. Coloring node 3 with Color 2, then update the staturation and degree of other node

Attachments:

Chapter09-V2.pdf