Question

Show that (1 |????| ?_???) can be solved to optimality without knowledge of the processing times p_j. Give an example that this is not true for the problem 1 || ??? ?_? ?_? .

Answer 1

answer

Single machine scheduling has attained most attention in theoretical scheduling studies. The understanding of the theories paves way for analyzing and better designing multi- machine systems. The following assumptions generally apply to build single machine scheduling models.

1. Machine is continuously available during scheduling period.

2.The machine processes jobs one at a time.

3. The other job related information is known before hand. This information may include due date of the job (d_j) and release time of the job (r_j).

4.In non-preemptive scheduling, jobs finish processing without interruption. In preemptive scheduling, jobs may be removed from the machine without finishing the operation.

(1 |????| ?_???) stands for MAXIMUM LATNESS WITH PROCEDURE PROBLEM

The scheduling problem has jobs that have precedence relationship among them. While scheduling jobs on the single machine, the objective is to minimize the maximum lateness (L_max). One of the well known solution methodology to solve this problem is based on the least remaining slack (RS) rule. This rule is applied to solve 1 | prec | L_max problem.

The RS_j can be computed as follows:

RS_j = d_j – p_j – t.

where,

RS_j = the remaining slack of job j. p_j = processing time of job j.

d_j = due date for job j.

t = time of the schedule,

The algorithm to implement the RS rules is as follows:

step 1: At time zero, set t = 0.

Step 2: From the given precedence graph, form the set of schedulable jobs.

Step 3: Calculate the RS values of these jobs.

Step 4: Select a job j having minimum value of RS_j and schedule it on the machine.

Step 5: Remove the recently scheduled job from the set schedulable jobs.

Step 6: If all jobs have been scheduled, STOP. Otherwise update the set of schedulable job from precedence graph. Update value of t. Go to step 3.

Example

Job (j)	1	2	3	4	5	6	7	8
pj	2	3	2	1	4	3	2	2
Dj	5	4	13	6	12	10	15	19

At time zero, t = 0. Set of schedulable jobs based on precedence graph are contains the following jobs: {1-2-5}. The computation for the RS values for these jobs is given in the table:

Job(j)	dj	Pj	t	RSj
1	5	2	0	3
2	4	3	0	1
5	12	4	0	8
			MIN(RSj)	1

Job 2 has the minimum RS value. Then, Job 2 is scheduled first on the machine at time 0 and it will be completed at time 3. Thus, updated the value of t to be = 3. The set S = {2}.

Next, job 6 is added to the Set of schedulable jobs. This means the set contains the following jobs: {1-5-6}. The computation for the RS values for these jobs in the set is given in the following table:

Job(j)	dj	pj	t	RSj
1	5	2	3	0
5	12	4	3	5
6	10	3	3	4
			MIN(RSj)	0

Since job 1 has the minimum RS value, then, it is scheduled second on time 3 the machine. The job will be completed ate time 5. Therefore, the updated value for t is = 5. The set S = {2-1}.

Next, job 4 is added to the schedulable jobs list. The set of schedulable jobs is {5-6-4}. Out of the three jobs in the set, job 4 has the minimum RS value as shown in the following table:

Job(j)	dj	Pj	t	RSj
4	6	1	5	0
5	12	4	5	3
6	10	3	5	2
			MIN(RSj)	0

Thus, job 4 is scheduled at time 5 and it will be completed at time 6. The set S = {2-1-4}. This will update the t value to be = 6. At this time, only two jobs are in the schedulable set. These jobs are {5-6}. Out of these two jobs, job 6 has the minimum RS value as shown in the following table:

Job(j)	dj	pj	t	RSj
5	12	4	6	2
6	10	3	6	1
			MIN(RSj)	1

Then, job 6 is scheduled at time 6 and it will be completed at time 9. The set S = {2-1-4-6}. This will updated the t value to be = 9. At this time, job 3 is added to the schedulable set. The jobs in the schedulable set are {5-3}. Out of these two jobs, job 5 has the minimum value of RS as shown in the following table:

Job(j)	dj	pj	T	RSj
3	13	2	9	2
5	12	4	9	-1
			MIN(RSj)	-1

Therefore, job 5 is scheduled at time 9 and completed at time 13. The set S ={2-1-4-6-5}. This will updated the value of t to be = 13. At this time, job 7 is added to the schedulable set of jobs. The set of schedulable jobs contains the following jobs: {3-7}. Out of these two jobs, job 3 has the minimum value of RS as shown in the following table.

Job(j)	dj	pj	t	RSj
3	13	2	13	-2
7	15	2	13	0
			MIN(RSj)	-2

Next, job 3 is scheduled at time 13 and it will be completed at time 15. The set S = {2-1-4-6-5-3}. The value of t is = 15. At this time, job 8 is added to the schedulable set. The set of schedulable jobs is {7-8}. Out of these two jobs, job 7 has the minimum value of RS as shown in the following table:

Job(j)	dj	pj	t	RSj
7	15	2	15	-2
8	19	2	15	2
			MIN(RSj)	-2

Thus, Job 7 is scheduled at time 15 and it will be completed at time 17. The set S = {2-1-4-6-5-3-7}. The value of t is = 17. The only unscheduled job is job 8 with RS value of 0 as shown in the following table:

Job(j)	dj	Pj	T	RSj
8	19	2	17	0
			MIN(RSj)	0

Then, job 8 is scheduled at time 17 and it will be completed at time 19. The schedulable job set is empty. Thus, STOP. The final sequence of jobs on the machine is as follows: {2-1-4-6-5-3-7-8}.