SEQUENCING - bikramjitgccbachd

SEQUENCING - bikramjitgccbachd

SEQUENCIN G PROBLEMS Sequencing A problem in which it is necessary to determine the orders or sequences of jobs in which they should be performed so as to minimize the total effectiveness on the sum of the pertinent costs is known as sequencing problems. A Sequencing problem could involve:

Jobs in a manufacturing plant Aircraft waiting for landing and clearance Maintenance scheduling in factory Programs to be run on computer Customers in a bank. a a TERMS USED: JOBS Jobs/items/customers are the primary stimulus for sequencing. Number of Machines a machine is characterized by a certain

processing capability or facilities through which a job must pass before it is completed in job. Processing Time It means the time each job requires at each machine. Total Elapsed Time It is the time Idle Time Processing It is the time the machine remains idle during the total elapsed time. Technological Order It refers to the order in which various machines are required for completing the jobs. It is also known as Processing order. No Passing Rule It implies that passing is not allowed i.e. the same order of the jobs is maintained over

each machine. If each of n-jobs are to be processed on 2 machines A & B in the order AB then this rule will JOB ARRIVAL PATTERN Job Arrival Pattern can be defined as the pattern in which a job arrives and joins the system. The arrival pattern may be fixed and known, variable but known and variable & unknown. Categories of Job Arrival Pattern: Static Arrival Pattern If all jobs arrive simultaneously. Dynamic Arrival Pattern Where the jobs arrive continuously. ASSUMPTIONS

No machine can process more than one job at a time. The processing times on different machines are independent of the order in which they are processed. The time involved in moving a job from one machine to another is negligibly small. Each job once started on a machine is to be performed upto completion on that machine. All machines are of different types. All jobs are completely known and are ready

for processing. A job is processed as soon as possible but Types of Sequencing Problems 1. Problems with n jobs through 2. 3. 4. 5. one machine. Problems with n jobs through two machines. Problems with n jobs through three machines. Problems with n jobs through m

machines. Problems with n jobs through one machine (dependent set up time) (as Assignment ). Problems with n jobs through one machine Method s Shortest Processing Time (SPT) Rule Weighted Scheduling Processing Time (WSPT) Rule

Problems with n jobs through 2 machines Methods Heuristic Method Combinato rial Method Heuristic Method Suggested by S.M.Johnson & Bellman. Procedure is as follows: 1. Select the smallest processing time occurring in the list Ai or Bj, if there is a tie select either of the smallest processing time. 2. If the smallest time is on machine A, then place it at first place if it is for the B machine place the

corresponding job at the last place. Cross off that job. 3. If there is a tie for minimum time on both the machines then select machine A first and machine B last and if there is tie for minimum on machine A (same machine) then select any one of these jobs first and if there is tie for minimum on machine B then select any of these jobs in the last. 4. Repeat step 2 & 3 to the reduced set of processing times obtained by deleting the processing time for both the machines corresponding to the jobs already assigned. 5. Continue the process placing the job next to the first or next to the last and so on till all jobs have been places and it is

called optimum sequence. 6. After finding the optimum sequence we can find the following: i. Total Elapsed Time = Total time between starting the first job of the optimum sequence on machine A and completing the last job on machine B. Combinatorial Method This method has three stages: 1. Compare operation time on machine A (ta) with machine B (tb). Give the code (Aa) 1 if ta > tb and code -1 if ta < tb. 2. Determine the minimum of the two operating time Ba, where Ba = min(ta, tb). 3. Give comparatic weightage of different jobs f(a), where f(a) = Aa/Ba. the optimal sequence for the job is

determined by arranging the jobs in ascending order of their weights f(a). Assumption the jobs have no priority i.e. no job is preferred to other job and storage space is available for all the jobs. Problems with n jobs on 3 machines Job 1 2 3 4 . . i . . n

Machine Machine Machine A B C A1 A2 A3 A4 . . Ai . . An B1 B2 B3

B4 . . Bi . . Bn C1 C2 C3 C4 . . Ci . . Cn

There is no general solution at present however previous method given by Johnson can be applied if the following two conditions are satisfied: Condition 1 Min Ai Max Bi and/ or Condition 2 Min Ci Max Bi Method: Replace given problem into 2 fictitious machines G & H where, Gi=Ai+Bi, Hi=Bi+Ci, and so on Now apply same procedure and find out optimal sequence. Problems with n jobs through m machines Job/ Machines A

B C. 1 2 3 4 5 A1 A2 A3 A4 A5 B1 B2

B3 B4 B5 n An Bn C1. C2. C3. C4. . C5. Cn. M

M1 M2 M3 M4 M5 Mn There is no solution available at present, however if any of the following conditions are met , we can proceed further: Condition 1 Min A Max B,C,M-1 and/ or Condition 2 Min M Max B,C,M-1 Method: Replace given problem into 2 fictitious machines G & H where, Gi=Ai+Bi+Ci+(M-1), Hi=Bi+Ci+(M-1)+M, and so on Now apply same procedure and find out

optimal sequence. Alternatively convert the given problem into a no. of 2 machine sub problems. Problems with n jobs through one machine (dependent set up time) These problems can be solved as the Assignment Problems using special case of Travelling Salesman. Problems with 2 jobs through m machines Graphical method is used for such type of problems. The steps are given below: 1. Construct a two dimensional graph where the X axis represent the processing time and sequence

of job 1 and the M1 machine; whereas, Y axis represents the processing tome and sequence of job 2 on M2 machine. It may be noted that scale used must be same for both the machines. 2. Shade the area where machine would be occupied by the two jobs at the same time. 3. The processing of both jobs can be represented by a continuous path which consists of horizontal, vertical and 45 degree diagonal segment. 4. The path starts at the lower left corner and stops at the upper right corner, while avoiding the shaded area in the graph. In other words, the path is not allowed to pass through shaded areas which correspond to operating both jobs concurrently on the same machine.

5. Any horizontal movement will indicate the progress of job 1 whereas job 2 is idle. 6. Any vertical movement will reveal that the job 2 is in progress while job 1 is idle.

Recently Viewed Presentations

  • The Future For Nuclear - Ecolo

    The Future For Nuclear - Ecolo

    Stephen Stretton. Dear Sir, Environmentalists for Nuclear Energy. A massive expansion in nuclear power is the only way to meet our CO2 goals and set an example to the rest of the earth, thus preventing dangerous climate change. Yours Sincerely,...
  • Evolution of Cells

    Evolution of Cells

    Elements of natural selection . All species have genetic variation.. Since organisms generally produce more offspring than can be supported by the environment, individuals within a species frequently complete with each other for survival.
  • The Baroque Era

    The Baroque Era

    Bacchus, one of Caravaggio's baroque paintings, depicts the youthful Roman god of wine. This painting resides in Florence at the Uffizi Gallery.The inedible fruit in the painting is thought to depict the idea that time moves quickly and life is...


    RAAF AERONAUTICAL INFORMATION SERVICE Comments on the DAFIF Terminal Procedure Coding for the Australian Airspace Mission Statement of RAAF AIS To provide the Australian Defence Force with tailored, accurate and current aeronautical information.
  • Comprehensive Community Services

    Comprehensive Community Services

    The CCS program will act in a Consumer advocacy role. CCS is a voluntary benefit and the individual must have the capacity to volunteer. An Assessment and IRP are completed to assist the CCS staff and consumer in crisis prevention...
  • صلاحیت های بالینی - آسکی

    صلاحیت های بالینی - آسکی

    Expanding our toolbox….. Knows Knows how Does Knows how Shows how Established technology of structured high fidelity in vitro simulations requiring behavioural performance (OSCE, SP-based testing, OSPE….) Expanding our toolbox…..
  • &quot;New Growth Theories&quot; Endogenous Growth Models

    "New Growth Theories" Endogenous Growth Models

    "New Growth Theories" Endogenous Growth Models J.D. Han King's University College UWO * * * * * * * * * * * * * * * * * * * * * * 1. Problems of Neo-Classical Growth Model...
  • Fostering greenfield mining-associated shared transport infrastructure through PPPs:

    Fostering greenfield mining-associated shared transport infrastructure through PPPs:

    International. Finance Corporation. ... strongly suggest a need for coordination between Governments and mining companies to develop affordable and bankable logistics solutions. Iron ore projects logistics challenges in West and Central Africa - a textbook case ...