CONTENTS 1.0 Introduction
2.0 Intended Learning Outcomes 3.0 Main Content
3.1 Terms Commonly Used
3.2 Types of Sequencing Problems 3.3 Priority Sequencing Rules
3.4 Sequencing n Jobs through Two Machines 3.5 n jobs 3 Machines Case
3.6 „n’ jobs „m’ Machines Case 4.0 Conclusion
5.0 Summary
6.0 Self-Assessment Exercises 7.0 References/Further Reading
1.0 INTRODUCTION
Every organisation wants to utilise its productive systems effectively and efficiently and maximise its profit by meeting the delivery deadlines. A number of jobs involving many operations have to be performed and there are limited resources in terms of plant and machinery on which the jobs have to be performed. It is necessary that available facilities are optimally utilised, loaded, scheduled and sequenced properly.
A sequence is the order in which different jobs are to be performed. When there is a choice that a number of tasks can be performed in different orders, then the problem of sequencing arises. Such situations are very often encountered by manufacturing units, overhauling of
CIT907 ADVANCED OPERATION RESEARCH
191
equipment or aircraft engines, maintenance schedule of a large variety of equipment used in a factory, customers in a bank or car servicing garage and so on.
The basic concept behind sequencing is to use the available facilities in such a manner that the cost (and time) is minimised. The sequencing theory has been developed to solve difficult problems of using limited number of facilities in an optimal manner to get the best production and minimum costs.
2.0 INTENDED LEARNING OUTCOMES At the end of this unit, you should be able to:
describe the concept of sequencing
state the assumptions made in the sequencing problem
define the terminologies used in sequencing problem
perform “Processing job through different number of machines”
perform “Processing of two job through m machines and n job through m machines”.
3.0 MAIN CONTENT
3.1 Terms Commonly Used
Job. This has to be sequenced, hence there should be a particular number of jobs (groups of tasks to be performed) say n to be processed
Machine. Jobs have to be performed or processed on machines. It is a facility which has some processing capability
Loading. Assigning of jobs to facilities and committing of facilities to jobs without specifying the time and sequence
Scheduling. When the time and sequence of performing the job is specified it is called scheduling
Sequencing. Sequencing of operations refers to a systematic procedure of determining the order in which a series of jobs will be processed in a definite number, say k, facilities or machines.
Processing Time. Every operation that is required to be performed requires definite amount of time at each facility or machine when processing time is definite and certain, scheduling is easier as compared to the situation in which it is not known
Total Elapsed Time. It is the time that lapses between the starting of first job and the completion of the last one.
Idle Time. The time for which the facilities or machine are not utilised during the total elapsed time.
Technological Order. It is the order which must be followed for completing a job. The requirement of the job dictates in which order various operations have to be performed, for example, painting cannot be done before welding.
Passing not allowed. If „n’ jobs have to be processed through ‘m’ machines in a particular order of M1, M2, M3 then each job will go to machine M1 first and then to M2 and finally to M3. This order cannot be passed.
Static arrival pattern. If all the jobs to be done are received at the facilities simultaneously.
Dynamic arrival pattern. Here the jobs keep arriving continuously.
Assumptions
In sequencing problems, the following assumptions are made:
All machines can process only one job at a time
No time is wasted in shifting a job from one machine to other
Processing time of job on a machine has no relation with the order in which the job is processed
CIT907 ADVANCED OPERATION RESEARCH
192
All machines have different capability and capacity
All jobs are ready for processing
Each job when put on the machine is completed
All job are processed in specified order as soon as possible 3.2 Types of Sequencing Problems
The following type of sequencing problems will be discussed in this unit:
n jobs one machine case
n jobs two machine case
n jobs ‘m’ machine case
Two jobs „m’ machine case
The solution of these problems depends on many factors such as:
The number of jobs to be scheduled
The number of machines in the machine shop
Types of manufacturing facility (slow shop or fast shop)
Manner in which jobs arrive at the facility (static or dynamic)
Criterion by which scheduling alternatives are to be evaluated
As the number of jobs (n) and the machines (m) increases, the sequencing problems become more complex. In fact, no exact or optimal solutions exist for sequencing problems with large n and m. Simulation seems to be a better solution technique for real life scheduling problems
n – Jobs one machine case
This case of a number of jobs to be processed on one facility is very common in real life situations. The number of cars to be serviced in a garage, number of engines to be overhauled in one workshop, number of patients to be treated by one doctor, number of different jobs to be machined on a lathe etc is the cases which can be solved by using the method under study.
In all such cases, we are all used to „first come first served‟ principle to give sense of satisfaction and justice to the waiting jobs. But if this is not the consideration, it is possible to get more favourable results in the interest of effectiveness and efficiency. The following assumptions are applicable:
The job shop is static
Processing time of the job is known.
The implication of the above assumption that job shop is static will mean that new job arrivals do not disturb the processing of n jobs already being processed and the new job arrivals should wait to be attended to in the next batch.
Shortest Processing Time (SPT) Rule
This rule says that jobs are sequenced in such a way that the job with least processing time is picked up first, followed by the job with the next smallest processing time (SPT) and so on.
This is referred to as shortest processing time sequencing. However, when the importance of the jobs to be performed varies, a different rule called Weight – Scheduling (WSPT) rule is used. Weights are allotted to jobs, greater weight meaning more important job. Let Wi be the weight allotted. By dividing the processing time by the weight factor, the tendency to move important job to an earlier position in the order is achieved.
CIT907 ADVANCED OPERATION RESEARCH
193 Weighted Mean Flow Time, WMFT =
n Wi fi 1
nW
i 1
Where fi = flow time of job i = Wi + ti ti = processing time of job i
WSPT rule for minimising weighted mean-flow time (WMFT) puts n jobs in a sequence such that
t
1
t
2
...
t
n
W
1
W
2
W
n
The numbers in brackets above define the position of the jobs in the optima sequence.
Example 1: Consider the 8 jobs with processing times, due dates and importance weights as shown below.
8 jobs one machine case data
Task Processing Due Date Importance ti
(i) Time (di) Weight (Wi) Wi
(ti)
1 5 15 1 5.0
2 8 10 2 4.0
3 6 15 3 2.0
4 3 25 1 3.0
5 10 20 2 5.0
6 14 40 3 4.7
7 7 45 2 3.5
8 3 50 1 3.0
From processing time ti in the table, the SPT sequence is 4 – 8 – 1 – 3 - 7 – 2 – 5 – 6 resulting in completion of these jobs at time 3, 6, 14, 20, 27, 36, 46, 60 respectively.
WMFT =
3 6 14 20 27 36 46 60
26.5hours 8
CIT907 ADVANCED OPERATION RESEARCH
194
The sequence is shown graphically above from which the number of tasks waiting as in-process inventory is seen to be 8 during 0-3-7,, during 3-6, 6, during 6-14; 5 during 14-20, 4 during 20-27, 3 during 27-36, 2 during 36 – 46 and one during 46-60. Thus the average inventory is given by:
8 3 7 3 6 8 5 6 4 7 3 9 2 10 114
60
24 21 48 30 28 27 20 14 212 3.53jobs
6060 WSPT
If the important weights Wi were to be considered, the WSPT could be used to minimise the Weighted Mean Flow Time (WMFT) to yield the sequence 3-4-8-2-7-6-5-1. This results by first choosing job with
minimum ti in the table. The respective flow time of jobs in this Wi
sequence is 6, 9, 12, 21, 28, 42, 52, and 58. Mean flow time is hours.
WMFT=
WMFT=
6 3 9 1 12 1 21 3 28 2 48 3 52 2 58 1
3 1 1 3 2 3 2 1
18 9 12 63 56 126 104 58 446 27.85hours
1616
CIT907 ADVANCED OPERATION RESEARCH
195
Example 2: Eight jobs A, B, C, D, E, F, and G arrive at one time to be processed on a single machine. Find out the optimal job sequence, when their operation time is given in below.
Job (n) Operation time in minutes
A 16
B 12
C 10
D 8
E 7
F 4
G 2
H 1
Solution: For determining the optimal sequence, the jobs are selected in a non-descending operation time as follows. Non-decreasing operation time sequence is H==>G==>F==> E==>D==>C==>B==>A
Total processing time H = 1
G = 1 + 2 = 3 F = 1 + 2 + 4 = 7 E = 1 + 2 + 4 + 7 = 14 D =1 + 2 + 4 + 7 + 8 = 22
C = 1 + 2 + 4 + 7 + 8 + 10 = 32 B = 1 + 2 + 4 + 7 + 8 + 10 + 12 = 44 A = 1 + 2 + 4 + 7 + 8 + 10 + 12 + 16 = 60
Average processing time = Total time/number of jobs = 183/8 = 23 minutes.
In case the jobs are processed in the order of their arrival i.e. H==>G==>F==>
E==>D==>C==>B==>A the total processing time would have been as follows:- A = 16
B = 16 + 12 = 28 C = 16 + 12 + 10 = 38 D = 16 + 12 + 10 + 8 = 46 E = 16 + 12 + 10 + 8 + 7 = 53 F = 16 + 12 + 10 + 8 + 7 + 4 = 57 G = 16 + 12 + 10 + 8 + 7 + 4 + 2 = 59 H = 16 + 12 + 10 + 8 + 7 + 4 + 2 + 1 = 60
Average processing time = 357/8 = 44.6, which is much more than the previous time.
3.3 Priority Sequencing Rules
The following priority sequencing rules are generally followed in production/service system:
First Come, First Served (FCFS). As explained earlier, it is followed to avoid any heart burns and avoidable controversies.
CIT907 ADVANCED OPERATION RESEARCH
196
Earliest Due Date (EDD). In this rule, top priority is allotted to the waiting job which has the earliest due/delivery date. In this case, the order of arrival of the job and processing time it takes is ignored.
Least Slack Rule (LS). It gives top priority to the waiting job whose slack time is the least. Slack time is the difference between the length of time remaining until the job is due and the length of its operation time.
Average Number of Jobs in the system. It is defined as the average number of jobs remaining in the system (waiting or being processed) from the beginning of sequence through the time when the last job is finished.
Average Job Lateness. Jobs lateness is defined as the difference between the actual completion time of the job and is due date. Average job lateness is sum of lateness of all jobs divided by the number of jobs in the system. This is also called Average Job Tardiness.
Average Earliness of Jobs. If a job is completed before its due date, the lateness value is negative and the magnitude is referred as earliness of job. Mean earliness of the job is the sum of earliness of all jobs divided by the number of jobs in the system.
Number of Tardy Jobs. It is the number of jobs which are completed after the due date.
3.4 Sequencing n Jobs through Two Machines
The sequencing algorithm for this case was developed by Johnson and is called Johnson‟s Algorithm. In this situation, n jobs must be processed through machines M1 and M2. The processing time of all the n jobs c: M1 and M2 is known and it is required to find the sequence which minimises the time to complete all the jobs.
Johnson‟s algorithm is based on the following assumptions:
There are only two machines and the processing of all the jobs is done on both the machines in the same order i.e. first on M1 and then on M2
All jobs arrive at the same time (static arrival pattern) have no priority for job completion. Johnson‟s Algorithm involves the following steps:
o List operation time for each job on machine M1 and M2.
o Select the shortest operation or processing time in the above list.
o If minimum processing time is on M1, place the corresponding job first in the sequence. If it is on M2, place the corresponding job last in the sequence. In case of tie in shortest processing time, it can be broken arbitrarily.
o Eliminate the jobs which have already been sequenced as a result of step 3 o Repeat step 2 and 3 until all the jobs are sequenced
Example 3
Six jobs are to be sequenced which require processing on two machines M1 and M2. The processing time in minutes for each of the six jobs on machines M1 and M2 is given below.
All the jobs have to be processed in sequence M1, M2. Determine the optimum sequence for processing the jobs so that the total time of all the jobs is minimal. Use Johnson‟s Algorithm.
Jobs 1 2 3 4 5 6
Processing Machine 30 30 60 20 35 45
Time M1
Machine 45 15 40 25 30 70 M2
Solution
Step I. Operation time or processing time for each job on M1 and M2 is provided in the question.
CIT907 ADVANCED OPERATION RESEARCH
197
Step II. The shortest processing time is 15 for job 2 on M2.
Step III. As the minimum processing time is on M2, job 2 has to be kept last as follows;
2 Step IV. We ignore job 2 and find out the shortest processing time
of the rest jobs. Now the least processing time is 20 minutes on machine M1 for 4. Since it is on M1, it is to be placed first as follows:
4 2
The next minimum processing time is 30 minutes for job 5 on M2 and Job 1 on M1. So job 5 will be placed at the end. Job 1 will be sequenced earlier as shown below.
4 1 5 2
The next minimum processing time 40 minutes for Job 3 on M2, hence it is sequenced as follows;
4 1 3 5 2
Job 6 has to be sequenced in gap or vacant space. The complete sequencing of the jobs is as follows:
4 1 6 3 5 2
The minimum time for six jobs on machine M1 and M2 can be shown with the help of a Gantt chart as shown below.
The above figure show idle time for M1 (30 minutes) after the last job
has been processed. Idle time for M2 is 20 minutes before job 4 is started and 5 minutes before processing 6 and finishing job 1. The percentage utilization of M1 = 250 – 30/250 = 88% M2 = 250 – 25/250 = 90%.
Example 4
CIT907 ADVANCED OPERATION RESEARCH
198
A book-binder has one printing press, one binding machine and manuscripts of seven different books. The time required for performing printing and binding operations for the different books is shown below:
Book Printing Time (days) Binding Time (days)
1 20 25
2 90 60
3 80 75
4 20 30
5 120 90
6 15 35
7 65 50
Decide the optimum sequence of processing the books in order to minimise total time.
Solution. Step 1. Minimum time is 15 days on printing press (M1) for job 6 so it will be sequenced earlier as shown
6
Step II. Now book 1 and 4 have the least time of 20 days on printing press (M1) so these two books will be sequenced as
6 1 4
Step III. After eliminating job 6, 1 and 4 least time is for job 7 on binding machine (M2) so it will be placed last in the sequence.
6 1 4 7
Step IV. Now book 2 has least time of 60 on M2, hence it will be
placed at the end.
6 1 4 2 7
Step V. Book 3 has the least time of 75 days on M2 so it will be
placed as below.
6 1 4 3 2 7
Step VI. Jobs 5 will be placed in the vacant place
6 1 4 5 3 2 7
Step VII. Total processing time can be calculated as follow:
Optimum Printing Binding Idle time
sequence for
of jobs Binding
(books) In Out In Out
6 0 15 15 50 15
1 15 35 50 75 -
4 35 55 75 105 -
5 55 175 175 265 70
3 175 255 265 340 -
2 255 345 345 405 5
7 345 410 410 460 5
Total idle time
CIT907 ADVANCED OPERATION RESEARCH
199
Printing = (460 – 410) = 50 days as the printing of last job (7) is finished on 410 days but binding finishes only after 460 days, so printing machine is idle for 50 days.
Binding = 15 + 70 + 5 + 5 = 95 days
Example 5: A manufacturing company has 5 different jobs on two machines M1 and M2. The processing time for each of the jobs on M1 and M2 is given below. Decide the optimal sequence of processing of the jobs in order to minimise total time.
Jon. No Processing Time
M1 M2
1 8 6
2 12 7
3 5 11
4 3 9
5 6 14
Solution: The shortest processing time is 3 on M1 for job 4 so it will be sequenced as follow 4
Next is job 3 with time 5 and M1, hence job 3 will be sequenced as
4 3
Next minimum time is for jobs 1 on M2, this will be sequenced last
4 3 1
After eliminating jobs 4, 3 and 1, the next with minimum time is job 5 on M1
so it will be placed as
4 3 5 1
Now job 2 will be sequenced in the vacant space
4 3 5 2 1
3.5 n jobs m Machines Case
Johnson‟s algorithm which we have just applied can be extended and made use of n jobs 3 machine case, if the following conditions hold good:
Maximum processing time for a job on machine M1 is greater than or equal to maximum processing time for the same job.
or Minimum processing time for a job on machine M3 is greater than or equal to maximum processing time for a job on machine M2
The following assumptions are made:
Every job is processed on all the three machines M1, M2 and M3 in the same order i.e. the job is first processed on M1 then on M2 and then on M3.
The passing of jobs is not permitted
Process time for each job on the machine M1, M2 and M3 is known.
In this procedure, two dummy machines M1‟ and M2‟ are assumed in such a manner that the processing time of jobs on these machines can be calculated as:
Processing time of jobs on M1‟ = Processing time (M1 + M2)