Moore's Procedure & Johnson's Procedure: Session 12

Moores Procedure
&
Johnsons procedure
SESSION 12
Sequencing Theory for A Single

Machines
Assuming that n jobs are to be processed through one machine. For each job i,
define the following quantities:
ti=Processing time for job i, constant for job i;
di=Due date for job i, constant for job i;
Wi=Waiting time for job i, the amount of time that the job must wait
before its processing can begin.
When all the jobs are processed continuously, W is the sum of the
i
processing times for all of the preceding jobs;
t1
t2
t3
t4
W4=t1+t2+t3
F4=W4+t4
Fi=Flow time for job i, the waiting time plus the processing time: Fi= Wi+ ti;
Li=Lateness of job i , Li= Fi- di, either positive or negative;
Ti=Tardiness of job i, the positive part of Li, Ti=max[Li,0] ;
Ei=Earliness of job i, the negative part of Li, Ei =max[- Li,0]

Machines
Minimizing the number of Tardy Jobs:
An algorithm from Moore(1968) that minimizes the
number of tardy jobs for the single machine problem.
Step1. Sequence the jobs according to the earliest due date to

obtain the initial solution. That is d[1] d[2],, d[n];
Step2. Find the first tardy job in the current sequence, say job [i]. If
none exists go to step 4.
Step3. Consider jobs [1], [2], , [i]. Reject the job with the largest
processing time. Return to step2. (Why ?)
Reason: It has the largest effect on the tardiness of the Job[i].
Step4. Form an optimal sequence by taking the current sequence

and appending to it the rejected jobs. (Can be appended in any
order?)
Yes, because we only consider the number of tardiness jobs
rather than tardiness.

Machines
Example 2
Job
Due date
15
23
20
30
Processing time
10
10
Solution
Job
Due date
15
Processing time
Completion
time
Longest processing
time
4
20
23
30
10
10
17
27
35
41

Machines
Longest processing
time
Example 2 :Solution (Cont.)

Job
Due date
20
23
30
Processing time
10
Completion time
17
25
31
Job
Due date
23
30
Processing time
Completion time
15
21
The optimal sequence: 2, 3, 4, 6, 5, 1 or 2, 3, 4, 6, 1, 5. In each

case the number of tardy jobs is exactly 2.

Machines
Example 3
Job
Processing time
Due date
11
Sequencing Theory for

A Single Machines
Example 3
Not
Step1: find the job scheduled last(sixth)
predecessor
Job
Processing time
Due date
11
=2+3+4+3+2+1=15
Tardiness
15-9=6
15-11=4
15-7=8
Step2: find the job scheduled fifth

Job
Processing time
Due date
=15-2=13
Tardiness
Not
predecessor
13-9=4
13-7=6

A Single Machines
Example 3
Step3: find the job
scheduled fourth
Not
predecessor
Job
Processing time
Due date
=13-4=9
Tardiness
Because job3 is
no longer on the
list, Job 2 now
because a
candidate.
2
9-6=3
9-7=2
Step4: find the job scheduled third

Job
Processing time
Due date
=9-1=8
Tardiness
Not
predecessor
Because job6 has
been scheduled, Job 4
now because a
candidate along with
Job 2.
2
8-6=2
8-7=1

A Single Machines
Example 3
Step5: find the job
scheduled second
Job
1
2
4
6
3
5
Not
predecessor
Job
Processing
time
Due date
The optimal sequence: 1-2-4-6-3-5
Processing
time
Flow
time
Due date
Tardiness
2
3
3
1
4
2
2
5
8
9
13
15
3
6
7
7
9
11
0
0
1
2
4
4
Maximum
tardiness
Sequencing Theory for Multiple

Machines
Assume that n jobs are to be processed through m
machines. The number of possible schedules is
astonishing, even for moderate values of both n and
m.
For each machine, there is n! different ordering of

the jobs; if the jobs may be processed on the
machines in any order, there are totally (n!)m possible
schedules. (n=5, m=5, 25 billion possible schedules)
Even with the availability of inexpensive computing

today, enumerating all feasible schedules for even
moderate-sized problems is impossible or, at best,
impractical.

Machines
Gantt chart
Suppose that two jobs, I and J, are to be scheduled on two machines, 1

and 2, the processing times are
Machine 1
Machine 2
Job I
Job J
Assume that both jobs must be processed first on machine 1 and then on
machine 2. There are four possible schedules.

Machines
Schedule
Total flow time
Mean flow time
Mean idle time
(5+9)/2=7
(4+4)/2=4
5.5
10
10
9.5
1.

Machines
Scheduling n Jobs on Two Machines
The optimal solution for scheduling n jobs on two
machines is always a permutation schedule.
A very efficient algorithm for solving the two-machine
problem was discovered by Johnson(1954).
Denote the machines by A and B

The jobs must be processed first on machine A and then on
machine B.
Define
Ai=Processing time of job i on machine A

Bi=Processing time of job i on machine B
Rule: Job i precedes job i+1 if min(Ai, Bi-1)<min(Ai+1,Bi)
List the values of Ai and Bi in two columns.

Find the smallest remaining element in the two columns. If it
appears in column A, then schedule that job next. If it appears in
column B, then schedule that job last.
Cross off the jobs as they are scheduled. Stop when all jobs have

Machines
Job
Example 4
Machine A
1
2
3
4
5
Optimal sequence : 2
Machine B
5
1
9
3
10
2
6
7
8
4
Principles of Work
Center / Job Shop
Scheduling
1. There is a direct
equivalence between work
and cash flow.
flow
2. The effectiveness of any job shop should be

measured by speed of flow through the shop.
3. Schedule jobs as a string, with process steps backto-back.
4. A job once started should not be interrupted.
5. Speed of flow is most efficiently achieved by
focusing on bottleneck work centers and jobs.
6. Reschedule every day.
Principles of Work
Center / Job Shop
Scheduling
7. Obtain feedback each day on jobs that are
completed at each work center
not
8. Match work center input information to what the

worker can actually do
9. When seeking improvement in output, look for
incompatibility between engineering design and
process execution
10.Certainty of standards, routings, and so forth is not
possible in a job shop, but always work towards
achieving it

Moore's Procedure & Johnson's Procedure: Session 12

Uploaded by

Copyright:

Available Formats

Moore's Procedure & Johnson's Procedure: Session 12

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Moore's Procedure & Johnson's Procedure: Session 12

Uploaded by

Copyright:

Available Formats

Moores Procedure

Sequencing Theory for A Single

ti=Processing time for job i, constant for job i;

di=Due date for job i, constant for job i;

Li=Lateness of job i , Li= Fi- di, either positive or negative;

Ti=Tardiness of job i, the positive part of Li, Ti=max[Li,0] ;

Ei=Earliness of job i, the negative part of Li, Ei =max[- Li,0]

Sequencing Theory for A Single

Step1. Sequence the jobs according to the earliest due date to

Step4. Form an optimal sequence by taking the current sequence

Sequencing Theory for A Single

Sequencing Theory for A Single

Example 2 :Solution (Cont.)

The optimal sequence: 2, 3, 4, 6, 5, 1 or 2, 3, 4, 6, 1, 5. In each

Sequencing Theory for A Single

Sequencing Theory for

Step2: find the job scheduled fifth

Sequencing Theory for

Step4: find the job scheduled third

Sequencing Theory for

The optimal sequence: 1-2-4-6-3-5

Sequencing Theory for Multiple

For each machine, there is n! different ordering of

Even with the availability of inexpensive computing

Sequencing Theory for Multiple

Suppose that two jobs, I and J, are to be scheduled on two machines, 1

Sequencing Theory for Multiple

Total flow time

Mean flow time

Mean idle time

Sequencing Theory for Multiple

Denote the machines by A and B

Ai=Processing time of job i on machine A

Rule: Job i precedes job i+1 if min(Ai, Bi-1)<min(Ai+1,Bi)

List the values of Ai and Bi in two columns.

Sequencing Theory for Multiple

2. The effectiveness of any job shop should be

8. Match work center input information to what the

You might also like