Scribd
Upload
21 views3 pages

Sequencing Problem in Job Processing

Uploaded by

techexplorers2020
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as ODT, PDF, TXT or read online on Scribd
21 views3 pages

Sequencing Problem in Job Processing

Uploaded by

techexplorers2020
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as ODT, PDF, TXT or read online on Scribd

Sequencing problem

sequencing problem is a problem in which it is to Determine the orders or sequence


of jobs in which they should be performed to minimize the total effectiveness of the
sum of the relevant costs.
Processing of n jobs on 2 machines
The simplest possible sequencing decision problem is that of n job 2 machine
sequencing.
In which, in jobs should be processed through 2 machines to minimize the total
elapsed time.
Let there be n jobs, each of which is to be processed through 2 machines say m1
and m2 in the order m1, m2
That means each job must pass through the sequence of operations.
First, a job is assigned on machine 1 and after the completion of the job on machine
m1 it assigned to the machine m2.
Suppose If the machine m2 is not free at the moment of processing the same job
then the job must wait for its tern on machine m2.
Here, passing not allowed due to that machine m1 will remain busy in processing all
the n jobs 1 by 1 while machine m2 may remain idle after completion of 1 job and
before starting another job.
Here the main objective is to reduce idle time of machine m2
Q1 7jobs go first over machine 1 and then over machine 2 processing time in hours
is given below
Jobs$p$q$r$s$t$u$v
M1$
M2$
Find the optimal sequence in which job should be processed
We can apply Johnsen algorithm for solving the sequencing problem
From the table we can find that the smallest processing time is 1 hour for job u on
machine 2
So, we should schedule the job u in the write hand side end of the table.
Delete the job u which has been sequenced in the table from the question
The reduced set processing time is given below
Processing of n jobs through 3 machines
This case is similar to the previous case accept that instead of 2 machines there are
3 machines
Each job is to be processed through 3 machines. Problems following under this
category can be solved by the method developed by Johnsen
Following are the 2 conditions of this approach:
1. Minimum of AI>=
maximum of BI
2. Minimum of CJ>=
maximum of BI
If either or both of the above conditions are satisfied then we replace the 3
machines by 2 machines G and H with corresponding processing time given by
G
¿
A
+ ¿ B

and
H
¿
B
+ ¿ C

After calculating the new processing time, we determine the optimal sequence of
jobs for the machines G and H in the usual manner
The company has to process 5 items on the 3 machines A, B, C, processing times
are given in the following table.
Item 1 2 3 4 5
A 4 9 8 6 3
B 4 5 3 2 6
C 6 9 11 8 7
Find the sequence that minimizes the total elapsed time
Since, the condition minimum of C >= maximum of b is satisfied, the problem can
be solved by the above procedure.
Now,
Item$1$2$3$4$5
G=A+B$
H=B+C$
Processing of n jobs through m machines
There is no general method which we can use to obtain optimal sequence in
problem involving processing of n jobs on m machines.
The method described below for solving n jobs and m machines sequencing
problem is applicable to only certain problems where the minimum cost of
processing the job through first and or last machine is more than equal to the cost
of processing the job through remaining machines.
So, we can describe the sequencing problem as follows:
1. There are n jobs denoted by 1, 2, 3, …, n to be performed.
2. Each of the jobs is to be processed through m machines
3. No passing of job is permitted.
The optimal sequence can be obtained if either 1 of condition or both conditions are
satisfied
1. Minimum of tij>=maximum of tij
2. Minimum of tmj >= maximum of tmj
Where j = 1, 2, …, n-1
If any one of the conditions is satisfied convert the m number machines types in to
a 2-machine type.

Common questions

Powered by AI

Replacing machines with new types G and H, where G equals the combined processing times of machines A and B and H equals the combined processing times of machines B and C, simplifies the sequencing problem. This method relies on specific conditions where minimum and maximum processing times guide the restructuring of the machine sequence. It facilitates the use of simpler algorithms for optimizing the job sequence, addressing the complexity of multiple machine scenarios by reducing them to a more manageable two-machine structure .

Conversion from a three-machine problem to a two-machine problem is achieved by creating two new machines G and H through the combination of specific machine processing times: G is the sum of processing times from machines A and B, while H is the sum from B and C. This conversion simplifies the problem by reducing the number of machines involved, allowing for the application of simpler sequencing solutions, thereby streamlining the optimization process and minimizing the total elapsed time .

The sequencing problem framework addresses cost minimization by structuring job sequences to reduce idle times and operation overlaps that lead to inefficiencies. By applying algorithms such as Johnsen's, which account for processing times and constraints, the framework ensures that the allocated sequence of jobs minimally impacts total costs by reducing wastage of machine resources and resulting in a more efficient overall processing time .

To apply the method for solving n jobs on m machines, a specific condition must be satisfied: the minimum processing time on the first or last machine must be greater than or equal to the processing time on the remaining machines. This condition allows converting the m-machine problem into a simpler two-machine problem by aggregating the processing times of the intermediate machines, thus making the optimization sequence more manageable .

The Johnsen algorithm can be adapted to three-machine sequencing problems by reducing the system to a two-machine problem if certain conditions are met: the minimum processing time on one machine (A or C) must be greater than the maximum processing time on the intermediate machine B. These conditions allow reassigning processing times to new machines G and H, simplifying the sequence optimization process .

The rule prohibiting job passing between machines ensures that each job follows a strict progression through the machines, thereby maintaining the integrity and order of operations. This rule is essential for accurately calculating processing times and optimizing sequences, as it prevents the disruption of machine schedules and potential conflicts that could arise from out-of-order processing .

These conditions imply that if the minimum processing time on machine A or C is greater than the maximum time on machine B, the problem can be simplified. These conditions permit the redefining of machine sequence flows by aggregating (or combining) processing times of certain machines, thereby reducing the complexity of multi-machine systems to a more tractable two-machine configuration. This optimization facilitates easier handling and better chances for minimizing total elapsed time in the sequencing process .

The Johnsen algorithm determines the optimal job sequence by examining the processing times of each job on both machines and selecting the job with the smallest processing time for completion first. The aim is to minimize idle time on the second machine and reduce the total elapsed time by strategically positioning jobs within the sequence according to their respective processing times .

The main limitations of the method for solving n jobs on m machines include its applicability restricted to specific problems where initial conditions of minimum and maximum processing times are met. It cannot be universally applied to all tuning configurations unless the conditions of problem reduction—such as converting multiple machines into two-machine problems—are satisfied, limiting its generalizability .

In sequencing problems with two machines, each job must be processed on the first machine (m1) before moving to the second machine (m2). The main challenge is minimizing idle time for the second machine (m2), as it may remain idle waiting for jobs to complete on the first machine. The Johnsen algorithm helps optimize this sequence by scheduling jobs based on their processing times, such as placing the job with the smallest processing time at the end of the sequence, thereby reducing the total elapsed time .

You might also like