Seqencing: Stochastic programming

Seqencing: Stochastic programming 

let us look to a problem, where we have to determine the order or sequence in which the jobs are to be processed through machines so as to minimize the total processing time. Here the total effectiveness, which may be the time or cost that is to be minimized is the function of the order of sequence. Such type of problem is known as SEQUENCING PROBLEM.

In case there are three or four jobs are to be processed on two machines, it may be done by trial and error method to decide the optimal sequence (i.e. by method of enumeration). In the method of enumeration for each sequence, we calculate the total time or cost and search for that sequence, which consumes the minimum time and select that sequence. This is possible when we have small number of jobs and machines. But if the number of jobs and machines increases, then the problem becomes complicated. It cannot be done by method of enumeration. Consider a problem, where we have ‘n‘ machines and ‘m’ jobs then we have (n!)m theoretically possible sequences. For example, we take n = 5 and m = 5, then we have (5!)5 sequences i.e. which works out to 25, 000,000,000 possible sequences. It is time consuming to find all the sequences and select optima among all the sequences.

Hence we have to go for easier method of finding the optimal sequence. Let us discuss the method that is used to find the optimal sequence. Before we go for the method of solution, we shall define the sequencing problem and types of sequencing problem. The student has to remember that the sequencing problem is basically a minimization problem or minimization model.

Assumptions Made in Sequencing Problems

Principal assumptions made for convenience in solving the sequencing problems are as follows:

(a) The processing times Ai and Bi etc. are exactly known to us and they are independent of order of processing the job on the machine. That is whether job is done first on the machine, last on the machine, the time taken to process the job will not vary it remains constant.

(b) The time taken by the job from one machine to other after processing on the previous machine is negligible. (Or we assume that the processing time given also includes the transfer time and setup time).

(c) Each job once started on the machine, we should not stop the processing in the middle. It is to be processed completely before loading the next job.

(d) The job starts on the machine as soon as the job and the machine both become idle (vacant). This is written as job is next to the machine and the machine is next to the job. (This is exactly the meaning of transfer time is negligible).

(e) No machine may process more than one job simultaneously. (This means to say that the job once started on a machine, it should be done until completion of the processing on that machine).

(f) The cost of keeping the semi-finished job in inventory when next machine on which the job is to be processed is busy is assumed to be same for all jobs or it is assumed that it is too small and is negligible. That is in process inventory cost is negligible.

(g) While processing, no job is given priority i.e. the order of completion of jobs has no significance. The processing times are independent of sequence of jobs.

(h) There is only one machine of each type.

 Types of Sequencing Problems

There are various types of sequencing problems arise in real world. All sequencing problems cannot be solved. Though mathematicians and Operations Research scholars are working hard on the problem satisfactory method of solving problem is available for few cases only. The problems, which can be solved, are:

(a) ‘n’ jobs are to be processed on two machines say machine A and machine B in the order AB. This means that the job is to be processed first on machine A and then on machine B.

(b) ‘n’ jobs are to be processed on three machines A,B and C in the order ABC i.e. first on machine A, second on machine B and third on machine C.

(c) ‘n’ jobs are to be processed on ‘m’ machines in the given order

(d) Two jobs are to be processed on ‘m’ machines in the given order.

‘N’ Jobs and Two Machines

If the problem given has two machines and two or three jobs, then it can be solved by using the Gantt chart. But if the numbers of jobs are more, then this method becomes less practical. (For understanding about the Gantt chart, the students are advised to refer to a book on Production and Operations Management (chapter on Scheduling).

Gantt chart consists of X -axis on which the time is noted and Y-axis on which jobs or machines are shown. For each machine a horizontal bar is drawn. On these bars the processing of jobs in given sequence is marked. Let us take a small example and see how Gantt chart can be used to solve the same.

NUMERICAL EXAMPLES

Numerical 1) A machine operator has to perform two operations, turning and threading, on a number of different jobs. The time required to perform these operations in minutes for each job is given. Determine the order in which the jobs should be processed in order to minimize the total time required to turn out all

the jobs.

Solution

The smallest element is 1 in the given matrix and falls under second operation. Hence do the 6 th job last. Next smallest element is 2 for the job 4 and falls under first operation hence do the fourth job first. Next smallest element is 3 for job 1 falls under first operation hence do the first job second. Like this go on proceed until all jobs are over. 

The optimal sequence is :

The Job idle time indicates that there must be enough space to store the in process inventory between two machines. This point is very important while planning the layout of machine shops.