9
Sequencing Models
9.1 INTRODUCTION AND BASIC ASSUMPTION
This chapter deals with situations in which the effectiveness measure (time, cost, distance, and so on) is a function of the order or sequence of performing a series of jobs (tasks). The selection of the appropriate order in which waiting customers may be served is called sequencing. A practical situation may correspond to an industry producing a number of products, each of which is to be processed through different machines, of course, finite in number.
Suppose there are n jobs to perform, each of which requires processing on some or all of m different machines. The effectiveness (that is, cost, time, mileage, and henceforth) can be measured for any given sequence of job at each machine, and the most suitable sequence is to be selected (which optimises the effectiveness measure) among all (n!)^{m} theoretically possible sequences.
Although theoretically, it is always possible to select the best sequence by testing each one, in practice, it is impossible because of the large number of computations involved. For example, if there are 4 jobs to be processed at each of the 5 machines (i.e., n = 4 and m = 5), the total number of theoretically possible different sequences will be (4!)^{5} = 7,962,624. So, easier methods of dealing with such problems are needed. That is, a technique which helps us arrive at an optimal sequence without trying all or most of the possibilities is needed.
9.1.1 Definition
Suppose there are n jobs (1, 2, 3, …, n) each of which has to be processed one at a time at each of m machines A, B, C, … The order of processing each job through machines is given (for example, job 1 is processed through machines, in the order A, C, B). The time that each job must require on each machine is known. The problem is to find a sequence (n!)^{m} number of all possible sequences (or combinations or order) for processing the jobs so that the total elapsed time for all the jobs will be minimum.
Mathematically, let
A_{i} = time for job i on machine A,
B_{i} = time for job i on machine B, and so on
T_{i} = time from start of first job to completion of the last job.
Then, the problem is to determine for each machine a sequence of jobs (i_{1}, i_{2}, …, i_{n}) where (i_{1} …, i_{n}) is the permutation of integers which will minimise T.
9.1.2 Terminology and Notations
Notation:
t_{ij} = processing time (time required) for job i on machine j
T = total elapsed time for processing all the jobs. This includes idle time, if any.
I_{ij} = Idle time on machine j from the end of job (i – 1) to the start of job i.
Terminology:
Number of machines: It means the service facilities through which a job must pass before it is completed.
For example, a book to be published has to be processed through composing, printing, binding, and so on. In this example, the book constitutes the job and the different processes constitute the number of machines.
Processing order: It refers to the order (sequence) in which given machines are required for completing the job.
Processing time: It is the time required by a job on each machine.
Idle time on a machine: It is the time for which a machine does not have a process; it is idle time from the end of job (i – 1) to the start of job i.
Total elapsed time: It is the time interval between starting the first job and completing the last job including the idle time (if any) in a particular order by the given set of machines.
No passing rule: It refers to the rule of maintaining the order in which jobs are to be processed on given machines. For example, if n jobs are to be processed on two machines M_{1} and M_{2} in the order M_{1} M_{2}, then each job should go to machine M_{1} first and then to M_{2}.
9.1.3 Assumptions
- No machine can process more than one operation at a time
- Each operation, once started, must be performed till completion.
- A job in an entity is even though it represents a lot of individual parts; no lot may be processed by more than one machine at a time.
- Each operation must be completed before any other operation, which following it, can begin.
- Time intervals for processing are independent of the order in which the operations are performed.
- There is only one of each type of machine.
- A job is processed as soon as possible subject to ordering requirements.
- All jobs are known and are ready to start processing before the period under consideration begins.
- The time required to transfer jobs between machines is negligible.
9.1.4 Solution of Sequencing Problems
At present, a solution of following cases are available:
- n jobs and two machines A and B, all jobs processed in the order AB.
- n jobs and three machines A, B and C, all jobs processed in the order ABC.
- Two jobs and m machines. Each job is to be processed through the machines in a prescribed order (which is not necessarily the same for both the jobs).
- Problem with n jobs and m machines.
We will discuss these cases in the following sections.
9.2 FLOW SHOP SCHEDULING
In flow shop scheduling problems, there are n jobs, each of which requires processing on m different machines. The order in which the machines are required to process a job is called process sequence of that job. In flow shop scheduling problems, all the jobs will have the same process sequence. However, the processing time of each operation in a job will be different from that of the other jobs. If an operation is absent in a job, then the processing time of that operation in that job is assumed as zero.
9.2.1 Characteristics of Flow Shop Scheduling Problem
- A set of multiple operation jobs is available for processing at time zero (each requires m operations and each operation requires a different machine).
- Set-up times for the operations are sequence independent and are included in processing times.
- Job descriptors are known in advance.
- m different jobs are continuously available.
- Each individual operation of jobs is processed until its completion without pre-emption.
9.2.2 Processing n Jobs Through Two Machines
Let there be n jobs, each of which is to be processed through two machines A and B in the order AB. That is, each job has to pass through the same sequence of operations. In other words, a job is assigned on machine A first and after it has been completely processed, it is assigned to machine B. If machine B is not free, then the job has to wait in a waiting line for its turn, that is, passing is not allowed. Therefore, machine A will remain busy in processing all the n jobs one-by-one while machine B may remain idle after completion of one job and before starting of another job. Thus, the objective is to minimise the idle time of the second machine. This can be achieved only by determining sequence of n jobs which are to be processed on the two machines A and B.
Johnson’s algorithm for n jobs through 2 machines
Step 1: List the jobs along with their processing times in a table as follows:
Step 2: Examine the columns for processing time on machines A and B, and find the smallest processing time in each column, that is, find out min (t_{1j}, t_{2j}) for all j
Step 3: (a) If the smallest processing time is for the first machine A, then place the corresponding job in the first available position in the sequence. If it is for the second machine, then place the corresponding job in the last available position in the sequence.
(b) If there is a tie in selecting the minimum of all the processing times, then there may be three situations:
- Minimum among all processing times is same for the machine, that is, min (t_{1j}, t_{2j}) = t_{1k} = t_{2r}, then process the k^{th} job first and the r^{th} job last.
- If the tie for the minimum occurs among processing times t_{1j} on machine A only, then select the job corresponding to the smallest job subscript first.
- If the tie for the minimum occurs among processing times t_{2j} on machine B, then select the job corresponding to the largest job subscript last.
Step 4: Remove the assigned jobs from the table. If the table is empty, stop and go to step 4. Otherwise, go to step 2.
Step 5: Calculate idle time for machine A and B.
- Idle time for machine A = (Total elapsed time) – (Time when the last job in a sequence finishes in machine A)
- Idle time for machine B = Time at which the first job in a sequence finishes on machine A + (time when the j^{th} job in a sequence starts on machine B) – (Time when the (j – 1)^{th} j on in a sequence finishes on machine B)
Step 6: The total elapsed time to process all jobs through two machines is given by Total elapsed time = Time when n^{th} job in a sequence finishes on machine B.
where, B_{2j} = Time required for processing j^{th} job on machine B.
I_{2j} = Time for which B remains idle after processing (j – 1)^{th} job and before starting work on the j^{th} job.
Example 1
There are five jobs, each of which is to be processed through two machines M_{1}, M_{2} in the order M_{1}, M_{2}, processing hours are as follows:
Determine the optimum sequence for the five jobs, and minimum elapsed time. Also, find the idle time of machines A and B.
Solution:
TABLE 9.1
Optimal sequence
Explanation: The minimum element (among all the elements) is 3 corresponding to job 1 occurring under machine A.
Next minimum element is 4 against the job 5 under machine A; so next, do job 5. Now, the minimum element is 5. But there is a tie. 5 occurs against jobs 3 and 4. But job 3 is chosen since the entry corresponding to 5 under machine B is 6 smaller than 7 found for job 4 under machine A.
Obviously, job 4 is chosen next and lastly the job 2 is chosen.
To find the minimum total elapsed time.
TABLE 9.2
Therefore, minimum elapsed time = 36 hrs.
Idle time for machine A = 36 – 27 = 9 hrs.
Idle time for machine B = 3 hrs.
Example 2
A book binder has one printing press, one binding machine, and the manuscripts of a number of different books. The time required to perform the printing and binding operations for each book are shown below. Determine the order in which books should be processed, in order to minimise the total time required to turn out all the books.
Solution: Here, the books will first go to the printing press and then on the binding machine. If P_{i}(i = 1, 2, …, 6) denotes the time in hours on the printing press and B_{i} (i = 1, 2, …, 6) the binding time for books, then since min {P_{i}, B_{i}} = 10, corresponding to B_{6}, book 6 will be processed in the last. Now, min {P_{i}, B_{i}} = 20, which corresponds to P_{4}. Hence, book 4 will be processed in the beginning. Now, the minimum of P_{i} and B_{i} is 30 which corresponds to P_{1} and B_{5}, that is, there is a tie for the minima. So, we place book 1 next to the first and book 5 next to last. Since smallest time is 50 for book 3, we place book 3 in the 3rd cell and the remaining book in the 4th cell getting the optimal sequence.
To find the minimum elapsed time:
TABLE 9.3
From table 9.3, it is clear that the minimum elapsed time is 430 hours. Idle time for the printing machine is 10 hours (from 420 hours to 430 hours) and that for binding machine is 20 + 40 = 60 hours.
Remark: It may be noted that the total elapsed time is equal to the sum of the idle time of the binding machine and the total processing time on it.
9.2.3 Processing n Jobs Through 3 Machines
The problem can be described as
- Only three machines A, B and C are involved.
- Each job is processed in the prescribed order ABC.
- Transfer of jobs is not permitted, that is, adhere strictly the order over the machine.
- Exact or expected processing time are given in Table 9.4.
TABLE 9.4
There is no general procedure available for obtaining optimal sequence in this case. Johnson’s method can be extended to cover special cases when either one or both of the following conditions hold:
- The minimum time on machine A ≥ the maximum time on machine B.
- The minimum time on machine C ≥ the maximum time on machine B.
The method is to replace the problem with an equivalent problem, involving n jobs and 2 imaginary machines G and H, and corresponding time G_{i} and H_{i} are defined by G_{i} = A_{i} + B_{i}, H_{i} = B_{i} + C_{i}.
If this problem with the prescribed ordering GH is solved, the resulting optimal sequence will also be optimal for the original problem.
Find the sequence that minimises the total elapsed time required to complete the following tasks:
Solution: We are given 7 jobs each of which is to be processed through 3 machines I, II and III in the order I, II, III.
Now,
Minimum time on machine I = 3
Maximum time on machine II = 5
Minimum time on machine III = 5
Since maximum time on machine II = minimum time on machine III, the given problem can be reduced to a problem of processing n jobs through two machines.
Thus, if G and H are two imaginary machines such that
G_{i} = M_{i1} + M_{i2}
H_{i} = M_{i2} + M_{i3} for i = 1, 2, …, 7
then the problem can be rewritten as the following 7 jobs and 2 machines problems.
Using the optimal sequence algorithm, the following optimal sequence can easily be obtained.
To find the minimum elapsed time:
TABLE 9.5
From Table 9.5, we observe that, the minimum total elapsed time is 59 hours.
Idle time is 13 hours for machine I,
37 hours for machine II, and
7 hours for machine III.
9.2.4 Processing n Jobs Through m Machines
Suppose there are n jobs to be processed through m machines, say M_{1}, M_{2}, …, M_{m} in the order M_{1}, M_{2} … M_{m}, and let T_{ij} denote the time taken by the i^{th} machine to complete the j^{th} job. There is no general method available by which we can obtain optimal sequence(s) in problems of this type. This problem can be converted to a problem of processing n jobs through 2 machines if no passing of jobs is permissible and if either or both of the conditions given in step 2 of the procedure that follows is satisfied:
Procedure for obtaining optimal sequence
Step 1: Find (i) , (ii) , and (iii) for j = 1, 2, … n
Step 2: Check whether
(i) for i = 2, 3, …, m – 1
or, (ii) for i = 2, 3, …, m – 1
Step 3: If inequations of Step 2 are not satisfied, this method fails. Otherwise, go to next step.
Step 4: Convert the m machine problem into a 2-machine problem considering two imaginary machines G and H, so that
T_{Gj} = T_{1j} + T_{2j} + … + T_{(m – 1)j} and
T_{Hj} = T_{2j} + T_{3j} + … + T_{Mj}Now, determine the optimal sequence on n jobs through 2 machines by using the optimal sequence algorithm.
Step 5: In addition to conditions given in Step 4, if T_{2j} + T_{3j} + … + T_{(m – 1)} = C (a fixed positive constant) for all j = 1, 2, …, n, then determine the optimal sequence for n jobs and two machines M_{1} and M_{m} in the order M_{1} M_{m} by using the Jhonson’s algorithm.
Remark:
- If in addition to the condition given in Step 4, T_{ij} = T_{mj} and T_{Gj} = T_{Hj}, for j = 1, 2, …, n, then n! number of optimal sequence will exist.
- This procedure for sequencing n jobs is not a general procedure. It is applicable to only to such those sequencing problems in which minimum time or cost of processing the jobs through first and/or last machine is greater than or equal to the time or cost of processing the jobs through the mediocre machine.
Example 1
There are 4 jobs each of which has to go through the machines M_{i}, i = 1, 2, …, 6 in the order M_{1} M_{2} … M_{6}. Processing time are given.
TABLE 9.6
Determine a sequence for these four jobs which minimises the total elapsed time T.
Solution: Here,
Hence, the conditions,
are satisfied. The problem can be converted into 4-job and 2-machine problem. Thus, if G and H are two imaginary machines such that and , then the problem can be reformulated as
TABLE 9.7
Using Johnson’s algorithm, an optimal sequence is obtained as C–A–B–D.
To find the minimum elapsed time:
TABLE 9.8
From Table 9.8, we observe that the minimum elapsed time is 130 hours.
Example 2
Four jobs 1, 2, 3 and 4 are to be processed on each of the four machines A, B, C and D in the order ABCD. The processing time in minutes are given in Table 9.9. Find for no passing, the minimum elapsed time.
TABLE 9.9
Solution: min A_{i} = 28, min D_{i} = 32, max B_{i} = 16 and max C_{i} = 18
Since min A_{i} ≥ Max B_{i};
min A_{i} ≥ max C_{i}; and
min D_{i} ≥ max B_{i};
min D_{i} ≥ max C_{i};
the problem can be converted to a 2-machine and 4-job problem.
Further, since B_{1} + C_{1} = B_{2} + C_{2} = B_{3} + C_{3} = B_{4} + C_{4} = 28, a fixed constant, the given problem reduces to that of finding the optimal sequence for 4 jobs and 2 machines A and D in the order AD. Machines B and C do not have any effect on the optimality of the sequence.
Examining columns A and D only, the optimal sequence is given by
3 – 2 – 1 – 4
To find the minimum elapsed time:
Use the individual processing time given in the original problem.
TABLE 9.10
Thus, the minimum elapsed time is 250 minutes.
9.3 JOB SHOP SCHEDULING
In job shop scheduling problems, we assume that each job has m different operations. If some of the jobs have less than m operations, the required number of dummy operations with zero process times is assumed. The process sequences of the jobs are not the same. Thus, the flow of each job in job shop scheduling is not unidirectional.
9.3.1 Difference between Flow Shop Scheduling and Job Shop Scheduling
Unlike the flow shop model, there is no initial machine that performs only the first operation of a job nor is there a terminal machine that performs only the last operation of a job in job shop scheduling. In flow shop scheduling, an operation number in the operation sequence of a job may be the same as the position number of the required machine. Hence, there is no need to distinguish between them. In contrast, in job shop scheduling, different jobs will have different operation sequences. So, a straight flow cannot be assumed for the job shop problem.
9.3.2 Processing Two Jobs on n Machines
Suppose there are two jobs, job 1 and job 2, each of which is to be processed on n machines M_{1}, M_{2}, … M_{n}.
General assumptions
- The technological ordering of each of the two jobs through n machines is known in advance (ordering may not be same for both the jobs).
- Each machine can process only one job at a time.
- The exact processing time on all the n machines are known.
Graphical method is used to determine the minimum total elapsed time.
Graphical method
Algorithm:
Step 1: Use the x-axis to represent the processing time for job 1 and the y-axis to represent the process time for job 2.
Step 2: Mark the machine time for the two jobs and their corresponding axes as per the given technological order.
Note that in such a graph moving horizontally will imply that job 1 is being processed while job 2 remains idle. Moving vertically will imply that job 2 is processed while job 1 remains idle. Diagonal movement along 45° line to the horizontal (line with slope 1) will imply that both the jobs 1 and 2 are being processed simultaneously. Since each machine can process only one job at a time, overlapping region for the machines should be determined first and movement across them should be avoided.
Step 3: An optimal path is the shortest one (that minimises the idle time for job 1 in the horizontal movement or the shortest one that minimises the idle time for job 2 in the vertical movement) consisting of horizontal, vertical and 45° lines from the origin to the end. Obviously, we must choose such a combination in which diagonal movement is maximum possible.
Step 4: Compute the total elapsed time by adding processing time of job 1 + idle time of job 1.
Or
Processing time of job 2 + idle time of job 2, and the optimal sequence of processing from the graph drawn.
Example 1
Determine the minimum time needed to process two jobs on four machines M_{1}, M_{2}, M_{3} and M_{4}. The technological order for these jobs as given below:
Processing time (in hours) are as given under:
Solution: The rectangular blocks in Figure 9.1 represent the overlaps (for clashes) which are to be avoided.
FIGURE 9.1
An optimal path is one that minimises the idle time for job 1 (horizontal movement). Similarly, an optimal path is one that minimises the idle time for job 2 (vertical movement).
Hence,
minimum elapsed time = processing of job 1 + idle time for job 1
= 25 + 6 = 31 hours.
Or
Minimum elapsed time = processing of job 2 + idle time for job 2
= 28 + 3 = 31 hours.
Sequence: Process both the jobs for 9 hours; process job 1 for 3 hours, process both the jobs for the next 13 hours; process job 2 only for 6 hours to complete all the jobs and their processing. Total elapsed time = 31 hours.
Example 2
Use graphical method to minimise the time needed to process the following jobs on the machines shown below, that is, for each machine find the job which should be done first. Also, calculate the total time needed to complete both the jobs.
TABLE 9.11
Solution: The rectangular blocks in the following figure represent the overlaps (clashes) which are to be avoided.
FIGURE 9.2
Minimum total elapsed time = processing of job 1 + idle time for job 1 = 17 + 3 = 20 hours.
Or, Minimum total elapsed time = processing of job 2 + idle time on job 2 = 20 + 0 = 20 hours.
Idle time for job 1 is 3 hours and that for job 2 is 0 hours. Process both the jobs for 9 hours and then perform job 2 for 3 hours and then perform both the jobs for 8 hours.
Example 3
Use graphical method to minimise the time required to process the following jobs on the machines, that is, for each machine specify the job which should be done first. Also, calculate the total elapsed time to complete both the jobs.
Solution: The rectangular blocks in Fig. 9.3 represent the overlaps (clashes) which are to be avoided.
FIGURE 9.3
Total elapsed time = 34 + 10 = 44 hours
Or,
= 40 + 4 = 44 hours
The optimal processing sequence for the two jobs on various machines is as follows:
Job 1 precedes job 2 on machine A,
Job 2 precedes job 1 on machine B,
Job 2 precedes job 1 on machine C,
Job 1 precedes job 2 on machine D, and
Job 2 precedes job 1 on machine E.
9.4 GANTT CHART
Consider the problem of processing n jobs through two machines M_{1} and M_{2} in the order M_{1} M_{2}. Let X_{i2} be the time for which machine M_{2} remains idle after finishing (i – 1)^{th} job and before starting the processing of i^{th} job (i = 1, 2, …, n). We know that total elapsed time is given by
Or,
where, M_{i2} is the total time for which M_{2} has to work and M_{i1} is the total time for which M_{1} has to work. The optimal sequence is one that minimises the idle time of the machines.
The optimum sequence of performing the jobs, and the time in and time out of the various jobs and the idle time on each machine can be best described by a Gantt Chart:
FIGURE 9.4
Example 1
Consider the sequencing problem given in Example 1 under Section 9.2. The optimal sequence of the job is 1–5–3–4–2, the total minimum elapsed time is 37 hours, idle time for machine A is 10 hours, and the idle time for machine B is 4 hours. Gantt Chart representation of the above problem is given in Fig. 9.5.
FIGURE 9.5 Gantt Chart
Remark: Gantt Chart can also be used to solve sequencing problem of processing 2 jobs on n machines.
Example 2
Two jobs are to be processed through four machines A, B, C, D with the following technological ordering:
Processing time (in hours) are given in the following table:
Find the minimum elapsed time for both jobs and also find the idle time for both jobs using a Gantt Chart.
Solution: In this method we draw the time taken for both jobs on different machines in the prescribed order. Care should be taken that no machines are busy simultaneously. The solution is given below:
FIGURE 9.6 Gantt Chart
Hence, minimum elapsed time is 160 hours, idle time for the chosen path is 40 for job 1 and 0 for job 2.
9.5 SHORTEST CYCLIC ROUTE MODELS (TRAVELLING SALESMEN PROBLEM)
A salesman has to visit a number of cities. The problem of finding the shortest route (in distance or time or cost) to visit all the cities (each city exactly once) is known as the Travelling Salesman Problem (TSP).
If the distance (time or cost) between every pair of cities is independent of the direction, the problem is said to be symmetrical. Otherwise, it is known as asymmetrical.
Example 1
It takes more time to go up a hill between two stations than come down the hill between them.
Example 2
A flight may take more time against the wind direction compared to that in the direction of the wind.
If there are n cities then there will be (n – 1)! possible routes. It may be noted that since the salesman has to visit all the n cities, the shortest route will be independent of the selection of the starting city.
Unfortunately, there is no analytical method which can be used satisfactorily to find the best route.
However, there are some computational techniques.
Some of the areas in which this type of problem arises consists of
- postal deliveries
- inspection
- school bus routing
- television relays
- assembly lines.
TSP appears to be related to the sequencing problem but actually is more similar to assignment problem with the difference that there is an additional constraint specifying that the solution should be in cyclic order. The solution methodologies of TSP are discussed in detail in Chapter 5.
9.6 SHORTEST ACYCLIC ROUTE MODELS (MINIMAL PATH PROBLEM)
TSP is a routing problem involving rather severe constraints. Another routing problem arises when we wish to go from one place to another or to several other places and we are to select the shortest route (involving least distance or time or cost) out of many alternatives to reach the desired station. Such acylic route network problems can be easily solved by the graphic method.
A network is defined as a set of nodes or nodes which are connected by lines or links. A way of going from one node (the origin) to another (the destination) is called a route or path. The links in a network may be one way (in either direction) or two way (in both directions). The numbers on the links in the network represent the time, cost or distance involved in traversing them. It is assumed that the way in which we enter a node has no effect on the way of leaving it—an assumption which does not hold good in TSP.
Example 1
Consider the network given below. A person wishes to reach the destination k while starting from the station a in the network. Links work in both directions unless marked otherwise. The numbers on the links represent cost (in rupees) of going from one node to another. Find the route that involves the least cost.
FIGURE 9.7
Solution: The given problem is not a TSP, but a shortest route problem. It is an acyclic route problem as it is not required to come back to the starting point a.
In order to find the shortest route between a and k we must find the shortest route from a to every other point in the network. The graphic method used for this purpose consists of the following steps:
Step 1: Identify the nodes having direct links with a and represent the cost from a on each of these nodes.
FIGURE 9.8
Step 2: In case there are links between any of the nodes obtained in Step 1, determine for each of these links if the indirect route from a is shorter than the direct route. Draw the shorter route as a solid line and the longer route as a dotted line. Insert the shortest cost found on each such node.
For example, the cost of going from a to g through d is lower than the cost of going from a to g directly. Hence, link ag is drawn as a dotted line. In case of a tie both links are represented by solid lines. Thus, one can go from a to d directly or through c at the same cost. Hence, the links connecting them are drawn solid as in Fig. 9.9.
FIGURE 9.9
Step 3: Add nodes to which one can go from the nodes represented in Step 2 and repeat Step 2. This is given in Fig. 9.10.
FIGURE 9.10
Step 4: Continue till completed. This is shown in Fig. 9.11. Solid lines show the routes that can be taken from a to every other node.
Evidently, there are a number of alternative paths giving least cost. They are:
(i) a – b – e – f – i – k (involving 6 nodes) (ii) a – c – f – i – k (involving 5 nodes) (iii) a – c – d – g – f – i – k (involving 7 nodes) (iv) a – d – g – f – i – k (involving 6 nodes) (v) a – d – g – i – k (involving 5 nodes) (vi) a – c – e – f – i – k (involving 6 nodes)
All the routes have the same cost (90) of travelling from a to k.
FIGURE 9.11
If, however, an additional constraint is imposed, for example, a person is to visit a minimum number of stations before reaching k, the number of alternative optimum (shortest) cost routes decreases to only two:
- a – c – f – i – k
- a – d – g – i – k
EXERCISES
Section 9.1
1. Define a sequencing problem.
2. Define the following terms:
- Number of machines
- Processing order
- Processing time
- Idle time on a machine
- Total elapsed time
3. What are the general assumptions of a sequencing model?
Section 9.2
4. Explain the Johnson’s algorithm of processing n jobs through two machines.
5. What is no passing rule in a sequencing algorithm?
6. Find the sequence that minimises the total elapsed time required to complete the following tasks on two machines:
[Answer: The optimal sequences are A C I B H F D G E and A C I H B F D G E. Minimum elapsed time is 61 hours and the idle time for machine II is 2 hours.]
7. Give three different examples of sequencing problems from your daily life.
8. Write a short note on the sequencing decision problem for n jobs on two machines.
9. We have five jobs, each of which must be processed on the two machines A and B in the order AB. Processing times in hours are given in the Table below:
Determine a sequence for the five jobs that will minimise the elapsed time T.
[Answer: Optimal sequence is 2 – 4 – 3 – 5 – 1, Elapsed time = 30 hours. Idle time for machine A = 2 hours, and for machine B = 3 hours.]
10. In a factory, there are six jobs to be performed, each of which should go through two machines A and B, in the order AB. The processing time (in hours) for the jobs are given. You are required to determine the sequence for performing the jobs that would minimise the total elapsed time T. What is the value of T?
[Answer: The optimal sequence is J_{1} – J_{6} – J_{2} – J_{3} – J_{4} – J_{5}; minimum elapsed time = 29 hours. Idle time for machine A is 3 hours and that for machine B is 1 hour.]
11. A company has 3 jobs on hand. Each of these must be processed through two departments, the sequential order for which is
Department A: Press shop Department B: Finishing
The Table below lists the number of days required by each job in each department.
Find the sequence in which the 3 jobs should be processed so as to take minimum time to finish all the 3 jobs.
[Answer: Optimal sequence is Job I – Job III – Job II, minimum elapsed time = 23 days.]
12. A company has six jobs on hand coded A to F. All the jobs have to go through 2 machines M_{1} and M_{2}. The time required for the jobs on each machine, in hours, is given below:
Draw a sequence table scheduling the six jobs on the two machines.
[Answer: Optimal sequence: A → F → D → B → C → E, Minimum elapsed time is 32 hours.]
13. We have 5 jobs each of which must go through 2 machines in the order AB. Processing time are given in the Table below:
Determine a sequence for the 5 jobs that will minimise the total elapsed time.
[Answer: 2 – 4 – 3 – 5 – 1, Total elapsed time (minimum) is 60 hours.]
14. Find the sequence that minimises the total elapsed time required to complete the following jobs:
[Answer: 3 – 1 – 5 – 6 – 2 – 4, Total time = 35 hours.]
15. Five jobs are performed, first on machine X and then on machine Y. The time taken in hours by each job on each machine is given below:
Determine the optimum sequence of jobs that minimises the total elapsed time to complete the jobs. Also, compute the minimum time.
[Answer: Optimal sequence B – D – C – E – A, minimum elapsed time = 48 hours, idle time is 12 hours each for machines X and Y.]
16. A manufacturing company processes 6 different jobs on two machines A and B. The number of units of each job and its processing times on A and B are given below:
Find the optimal sequence, the total minimum elapsed time and the idle time for each machine.
[Answer: Optimal sequence: 4(5 units) – 1(3 units) – 3(2 units) – 6(3 units) – 5(2 units) – 2(4 units); elapsed time = 159 minutes; idle time for machine A = 17 minutes, and for machine B = 3 minutes.]
17. A company plans to fill 6 positions. Since the positions are known to vary considerably with respect to skill and responsibility, different types of aptitude tests and interviews are required for each. While the aptitude tests are conducted by people from the clerical positions, the job interviews are held by the personnel from the management cadre. The job interviews immediately follow the aptitude test. The time required (in minutes) by each of the positions is given below:
In order to minimise the waiting time of the management personnel, in what order should the position filling be handled?
[Answer: Optimal sequence is P_{2} – P_{3} – P_{5} – P_{6} – P_{4} – P_{1}; minimum elapsed time is 7 hours and 20 minutes.]
18. A company has 8 large machines which receive preventive maintenance. The maintenance team is divided into two crews A and B. Crew A takes the machine ‘power’ and replaces parts according to a given maintenance schedule. The second crew resets the machine and puts it back into operation. At all times the no passing rule is considered to be in effect. The servicing times for each machine are given below:
Determine the optimal sequence of scheduling the factory maintenance crews to minimise their idle time and represent it on a chart.
[Answer: b – a – e – c – d – f – h – g.]
19. Given the following data:
- Order of processing Job: ACB.
- Sequence suggested: Jobs 5, 3, 6, 2, 1, 4
- Determine the total elapsed time for the sequence suggested.
- Is the given sequence optimal?
- If you answer to (ii) is no determine the optimal sequence and the total elapsed time associated with it.
[Answer: b (i) 73 hours; (ii) No; (iii) Optimal sequence is 1 – 3 – 2 – 4 – 6 – 5 and elapsed time is 67 hours.]
20. We have 5 jobs, each of which must go through machines A, B and C in the order ABC. Processing times (in hours) are given in the following Table.
Obtain the optimal sequence
[Answer: Optimal sequence is 3 – 2 – 4 – 1 – 5, minimum elapsed time is 51 hours.]
21. (a) A book binder has one printing press, one binding machine and the manuscripts of a number of different books. The times required to perform the printing and binding operation for each book are known. Determine the order in which the books should be processed in order to minimise the total time required to process all the books. Also, find the total time required.
(b) Suppose that an additional operation is added to the process described in (a), namely, finishing. The time required for the operations are given below:
What is the order in which the books should be processed? Also, find the minimal total elapsed time.
[Answer: | (a) Optimal sequence is 1 – 2 – 5 – 4 – 3; minimum elapsed time is 5 hours and 40 minutes. | |
(b) Optimal sequence is 5 – 1 – 4 – 2 – 3; minimum elapsed time is 8 hours and 30 minutes.] |
22. A readymade garments manufacturer has to process 7 items through 2 stages of production, namely, cutting and sewing. The time taken for each of these at the different stages is given below in appropriate units:
- Find the order in which these items are to be processed through these stages so as to minimise the total processing time.
- Suppose a third stage of production is added, namely, pressing and packing with the following processing time:
Find the order in which these 7 items are to be processed so as to minimise the time taken to process all the items through all the three stages.
[Answer: | (a) 3 – 5 – 7 – 2 – 6 – 1; minimum time is 46 hours. | |
(b) 1 – 4 – 3 – 6 – 2 – 5 – 7; minimum time is 86 hours.] |
23. Find the sequence for the following 8 jobs that will minimise the total elapsed time for the completion of all jobs. Each job is processed in the order CAB.
The entries give the time in hours on the machines.
[Answer: Optimal sequence is 4 – 5 – 3 – 1 – 2 – 8 – 7 – 6; minimum total elapsed time is 61 hours.]
24. A firm works 40 hours a week and has a capacity of overtime work to the extent of 20 hours in a week. It has received 7 orders to be processed on 3 machines A, B and C in the order ABC, to be delivered in a week’s time. The process times (in hours) are recorded in the following Table:
The manager, who, in fairness, insists on performing the jobs in the sequence in which they are received is refusing to accept an eighth order, which requires 7, 2 and 5 hours, respectively on A, B and C machines, because according to him the eighth job would require a total of 61 hours for processing, which extends the firm’s capacity. What is your advice to him?
[Answer: Optimal sequence is 7 – 1 – 4 – 8 – 2 – 3 – 5 – 6 or, 7 – 1 – 8 – 4 – 2 – 3 – 5 – 3 and minimum time is 57 hours.]
25. A company has 6 jobs which go through 3 machines X, Y and Z in the order XYZ. The processing time in minutes for each job on each machine is as follows:
What should be the sequence of jobs?
[Answer: Optimal sequence is 2 – 1 – 4 – 6 – 5 – 3 minimum time = 209 min; idle time: 34 min. for X, 159 min. for Y, and 44 min. for Z.]
26. Find the sequence that minimises the total elapsed time (in hours) required to complete the following jobs on three machines M_{1}, M_{2} and M_{3} in the order M_{1} M_{2} M_{3}.
[Answer: Optimal sequence A – D – E – B – C or, A – E – D – B – C or, D – A – E – B – C or, D – E – A – B – C or, E – D – A – B – C or, E – A – D – B – C. Minimum time: 51 hours; idle time: 9 hours for I, 31 hours for II, 19 hours for III.]
27. There are 5 jobs, each of which is to be processed through 3 machines A, B and C in the order ABC. Processing time in hours are:
Determine the optimum sequence for the 5 jobs and the minimum elapsed time.
[Answer: The optimal sequence: 4 – 1 – 5 – 2 – 3 or, 4 – 5 – 1 – 2 – 3 or, 1 – 4 – 5 – 2 – 3 or, 1 – 5 – 4 – 2 – 3 or, 5 – 1 – 4 – 2 – 3 or, 5 – 4 – 1 – 2 – 3. The minimum elapsed time is 44 hours; idle time: 17 hours for machine A, 29 hours for machine B and 7 hours for machine C.]
28. Four jobs 1, 2, 3 and 4 are to be processed on each of the five machines A, B, C, D and E in the order ABCDE. Find the total minimum elapsed time if no passing of jobs is permitted.
[Answer: Optimal sequence is 1 – 3 – 2 – 4. The minimum elapsed time is 51 time units; Machines A, B, C, D and E remains idle for 25, 33, 37, 35 and 18 time units, respectively.]
29. Solve the following sequencing problem giving an optimal solution when no passing is allowed.
[Answer: Optimal sequence is 2 – 4 – 5 – 1 – 3. Minimum elapsed time is 76 time units; idle time: 25, 51, 61, 15 time units, respectively.]
30. Solve the following problem giving an optimal solution when passing is not allowed.
[Answer: | (a) A – C – B – D, minimum time = 67 hours | |
(b) D – A – B – C, minimum time = 25 hours | ||
(c) 4! = 24 sequences, minimum time = 84 hours.] |
31. the optimal sequence for processing the jobs J_{1}, J_{2}, J_{3}, J_{4} on four machines M_{1}, M_{2}, M_{3} and M_{4}, in that order. The processing time are given as under.
[Answer: J_{4} – J_{3} – J_{2} – J_{1}; minimum elapsed time is 149 hours.]
32. Six jobs J_{1}, J_{2},…, J_{6} are required to be processed on 4 machines M_{1}, M_{2}, M_{3} and M_{4}, in that order. Using the processing time given below determine the optimal sequence(s) of the job performance.
[Answer: Optimal sequence is J_{4} – J_{2} – J_{5} – J_{1} – J_{3} – J_{6} or, J_{4} – J_{2} – J_{5} – J_{1} – J_{6} – J_{3}.]
33. Solve the following sequencing problem giving an optimal solution if passing is not allowed.
[Answer: Optimal sequence is D – C – B – A; minimum total elapsed time = 82 time units; idle time: 40 time units for M_{1}; 56 time units for M_{2}: 53 time units for M_{3}; and 19 time units for M_{4}.]
34. Find the optimal solution for the following sequencing problem:
[Answer: Optimal sequence C – B – D – A or, C – B – D; minimum total elapsed time = 86 time units. Idle time = 25 time units for M_{1}, 74 time units for M_{2}, 63 time units for M_{3}, 25 time units for M_{4}.]
Section 9.3
35. the graphical method to minimise the time added to process the following jobs on the machines shown, that is, for each machine find the job which should be done first. Also, calculate the total time elapsed to complete both the jobs.
[Answer: Minimum elapsed time = 22 hours; idle time for Job 1 = 5 hours; idle time for Job 2 = 2 hours.]
36. There are 2 jobs to be processed through 4 machines A, B, C, D. The technological ordering of the jobs is as follows:
Job 1 : | ABCD | |
Job 2 : | DBAC |
Processing time in hours is in the following Table.
Calculate the total minimum elapsed time to complete the two jobs.
[Answer: Total minimum elapsed time = 21 hours.]
37. Two jobs are to be processed on four machines A, B, C and D. The technological order for those machines is as follows:
Processing time in hours are given in the following Table.
Find the optimal sequence of jobs on each of the machines.
[Answer: Total minimum elapsed = 26 hours.]
38. A machines job has four machines A, B, C and D. Two jobs must be processed through each of these machines. The time (in hours) taken on each of the machines and the necessary sequences of jobs through the shop are given below:
Use graphic method to obtain the total minimum elapsed time.
[Answer: Minimum total elapsed time is = 15 hours.]
39. Two jobs are to be processed through four machines A, B, C, D with the following technological ordering.
Processing time (in hours) is given in the following Table:
Find the minimum processing time and the idle time for both the jobs.
[Answer: Minimum elapsed time is = 160 hours. Idle time for the chosen path is 40 for Job 1 and for Job 2.]
Section 9.6
40. Find the shortest route from a to i by using graphic method. The numbers on the links represent the distance in kilometers.
[Answer: a–c–e–g–i, 29 km.]
41. Find the shortest route from 0 to 8 by using the graphic method. The numbers on the links represent the distance in kilometers.
[Answer: Best route is 0–1–2–3–6–8; and the minimum distance is 17 km.]