Module 7. Sequencing problem

Lesson 14

INTRODUCTION AND GENERAL NOTATIONS

14.1  Introduction

Sequencing problems are concerned with an appropriate order (sequence) for a series of jobs to be done on a finite number of service facilities (like machines) in some well-defined technological order so as to optimize some efficiency measure such as total elapsed time or overall cost etc. In such cases, the effectiveness is a function of the order or sequence in which the tasks are performed. The effectiveness may be measured in terms of cost, time or mileage etc. A sequencing problem could involve jobs in a manufacturing plant, aircraft waiting for landing and clearance, maintenance scheduling in a factory, programmers to be run on a computer centre, customers in a bank, and so forth.

14.2  Sequencing

In Sequencing we are concerned with a situation where the effectiveness measure is a function of the order or sequence in which a series of tasks or jobs are performed. Suppose we have n jobs (1,2,3,---,n), each of which has to be processed or performed one at the time on each of m machines A,B,C,---. The order (sequence) of processing each job through the machines as well as the actual or expected time required by the jobs on each of the machine is also given. The effectiveness in terms of cost, times or mileage etc. can be measured for any given sequence of jobs at each machine and our aim is to select the most suitable sequence (which optimizes the effectiveness measure) among all theoretical possible sequences whose number will be (n!)^m. Although theoretically it is always possible to select the best sequence by testing each one but it is practically impossible due to large number of computations. Hence we have to compute effectiveness for each of (n!)^m sequences before selecting the most suitable one. But this is practically impossible to do. Let us explain as to what the sequencing problem is.

14.2.1  Problem of sequencing

Definition

Suppose there are n jobs (1, 2, ---, 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 the machines is given (for example, Job 1 is processed through machines A, C, B, - in that order). The time required for each job at each machine is also given. The problem is to find among (n!)^m number of all possible sequences (or combinations) that sequence (or order) for processing the jobs so that the total elapsed time for all the jobs will be a minimum. Mathematically, let us define:

 A_i = Time for i^th job on machine A ∀ i

 B_i = Time for i^th job on machine B ∀ i

 T = Time from start of the first job to completion of the last job

We wish to determine for each machine a sequence (i₁,i₂, … … … … i_n) where (i₁,i₂, … … … … i_n) is a permutation of the integers (1,2, .. … … n) which will minimize total elapsed time T.

14.3  Basic Terminology and Notations

The following terminology and notations will be used in this unit:

14.3.1  Number of machines

It means service facilities through which a job must pass before it is completed. In a milk plant, milk packed in pouches has to be processed through boiling, cooling, packaging etc. In this milk packing in pouches constitutes the job and various processes constitute the number of machines.

14.3.2  Processing time

It means the time required by each job on each machine.  It is denoted by T_ij which means processing time required by the i^th machine (i=1, 2, 3---, n; j=1, 2, 3---, m).

14.3.3  Processing order

It refers to the order in which various machines are required for completing the job.

14.3.4  Idle time on a machine

This is the time a machine remains idle during the total elapsed time. Let X_ij denote the idle time of machine j between the end of (i-1) ^th job and the start of i^th job.

14.3.5  Total elapsed time

This is the time 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. This will be denoted by T.

14.3.6  No passing rule

It means that passing is not allowed i.e. same order of jobs is maintained over each machine. If each of the n jobs is to be processed through two machines A and B in the order AB then this means that each job will go to machine A and then to B.

14.4  Basic Assumptions of Sequencing Problem

o No machine can process more than one operation at a time.

o Each job once started on a machine is to be performed up to its completion on that machine.

o A job is an entity i.e. even though the job represents a lot of individual parts, no lot may be processed by more than one machine at a time.

o The time intervals for processing are independent of the order in which the operations are performed.

o There is only one of each type of machine.

o A job is processed as soon as possible subject only to ordering requirements.

o All jobs are known and are ready to start processing before the period under consideration begins.

o The processing times are on different machines are independent of the order of the job in which they are to be processed.

o The time taken by the jobs in moving from one machine to another is very negligible and is taken as equal to zero.