Production Planning and Control
Section Two: Operations Scheduling
Got ready by Kirubel Bruck (PhD)
Scheduling
• Scheduling is the process establishing the
timing of the use of equipment, facilities, and
human activities in an organization.
• Operations scheduling is concerned with the
short-term control of activities to the
provision of goods and services.
• The output of scheduling is a timetable for
performing work.
Types of scheduling
• There are two general approaches to
scheduling: forward scheduling and backward
scheduling.
– Forward scheduling means scheduling ahead from
a point in time;
– Backward scheduling means scheduling backward
from a due date.
Forward and Backward scheduling
Types of activities in Scheduling
• An operations scheduling and control system
generally involves three types of activities:
– Loading
– Sequencing
– Scheduling
Loading
• Refers to the assignment of jobs to processing
(work) centers.
• Two different approaches are used to load work
centers: infinite loading and finite loading.
– Infinite loading assigns jobs to work centers without
regard to the capacity of the work center.
– Finite loading projects actual job starting and
stopping times at each work center, taking into
account the capacities of each work center and the
processing times of jobs, so that capacity is not
exceeded.
Infinite and Finite Loading
Loading – The Assignment Method
• The assignment model is a special purpose linear
programming model that is useful in situations
that call for assigning tasks or other work
requirements to resources.
– Typical examples include assigning jobs to machines or
workers, territories to salespeople, and repair jobs to
repair crews.
• The idea is to obtain an optimum matching of
tasks and resources. Commonly used criteria
include costs, profits, efficiency, and
performance.
Example - Assignment method to Loading
• Determine the optimum assignment of jobs to
workers for the following data
Solution
Step 1
• Subtract the smallest number in each row from every number in the row, and
enter the results in a new table.
Step 2
• Subtract the smallest number in each column from every number in the
column, and enter the results in a new table. The result of this column
reduction is
Solution continued
Step 3
• Deter mine the minimum number of lines needed to cross out all
zeros. (Try to cross out as many zeros as possible when drawing
lines.)
Since only three lines are needed to cross out all zeros and the table has
four rows, this is not the optimum. Note that the smallest uncovered value
is 1.
Solution continued
Step 4
• Subtract the smallest uncovered value from every uncovered number that
hasn’t been crossed out, and add it to numbers that are at the intersections of
covering lines.
Step 5
• Determine the minimum number of lines needed to cross out all zeros (four).
Since this equals the number of rows, you can make the optimum assignment.
Solution continued
Step 6
• Make assignments: Start with rows and columns with only
one zero. Match jobs with machines that have a zero cost.
Sequencing
• Sequencing is concerned with determining job
processing order.
• Sequencing decisions determine both the
order in which jobs are processed at various
work centers and the order in which jobs are
processed at individual workstations within
the work centers.
Sequencing - Single Machine Scheduling
(n jobs, one processor)
• In this problem, all the jobs will have the same processor.
• The basic single machine scheduling problem is characterized by the
following conditions (assumptions):
– The set of jobs is known; no new jobs arrive after processing begins;
and no jobs are canceled.
– Processing times are deterministic rather than variable.
– There will be no interruptions in processing such as machine
breakdowns, accidents, or worker illness.
– A set of independent, single-operation jobs is available for processing
at time zero.
– Set-up time of each job is independent of its position in jobs
sequence. So, the set-up time of each job can be included in its
processing time.
– Job descriptors are known in advance
– One machine is continuously available and is never kept idle when
work is waiting.
Possible priority rules
• The possible priority rules which are used in the single
machine scheduling are listed below
– First come, first served (FCFS):
– Shortest processing time (SPT)
– Earliest due date (EDD)
– Critical ratio (CR): Jobs are processed according to smallest ratio
of time remaining until due date to processing time remaining.
– Slack per operation (S/O): Jobs are processed according to
average slack time (time until due date minus remaining time to
process). Compute by dividing slack time by number of
remaining operations, including the current one.
– Longest processing time (LPT): The longer, bigger jobs are often
very important and are selected first.
– Rush: Emergency or preferred customers first
Measure of Performance
• The different common measure of performance which are
used in the single machine scheduling are listed below:
– Job flow time: is the amount of time it takes from when a job
arrives until it is complete. The average flow time for a group of
jobs is equal to the total flow time for the jobs divided by the
number of jobs.
– Job lateness: is the amount of time the job completion date is
expected to exceed the date the job was due or promised to a
customer.
– Makespan: is the total time needed to complete a group of
jobs. If processing involves only one work center, makespan will
be the same regardless of the priority rule being used.
– Average number of jobs: Jobs that are in a shop are considered
to be work-in-process inventory. The average work-in-process
for a group of jobs can be computed using the following
formula:
Average number of jobs = Total flow time / Makespan
Example
• Processing times (including setup times) and due dates for six jobs
waiting to be processed at a work center are given in the following
table. Assume jobs arrived in the order shown. Determine the
sequence of jobs, the average flow time, average tardiness, and
average number of jobs at the work center, for each of these rules:
a) FCFS
b) SPT
c) EDD
d) LPT
Job Processing time (days) Due date (days from present time)
A 2 7
B 8 16
C 4 4
D 10 17
E 5 15
F 12 18
Solution - FCFS
• The FCFS sequence is simply A-B-C-D-E-F.
The Makespan is 41 days
The measures of effectiveness are as follows:
(1) Average flow time: 120/6 = 20 days.
(2) Average tardiness: 54/6 = 9 days.
(3) Average number of jobs at the work center: 120/41= 2.93.
Solution - SPT
• Using the SPT rule, the job sequence is A-C-E-B-D-F
The resulting values for the three measures of effectiveness are
(1) Average flow time: 108/6 = 18 days.
(2) Average tardiness: 40/6 = 6.67 days.
(3) Average number of jobs at the work center: 108/41= 2.63.
Solution - EDD
• Using earliest due date as the selection criterion, the
job sequence is C-A-E-B-D-F.
The measures of effectiveness are as follows:
(1) Average flow time: 110/6 = 18.33 days.
(2) Average tardiness: 38/6 = 6.33 days.
(3) Average number of jobs at the work center: 110/41 = 2.68.
Solution - EDD
• Using the LPT rule, the job sequence is F-D-B-E-C-A.
The measures of effectiveness are as follows:
(1) Average flow time: 179/6 = 29.83 days.
(2) Average tardiness: 118/6= 19.67 days.
(3) Average number of jobs at the work center: 179/41 = 4.37.
Comparison of the four rules for the example
In this Example, the SPT rule was the best according to two of the measures of
effectiveness and a little worse than the EDD rule on average tardiness. For a
different set of numbers, the EDD rule (or perhaps another rule not mentioned
here) might prove superior to SPT in terms of average job tardiness or some
other measure of effectiveness. However, SPT is always superior in terms of
minimizing flow time and, hence, in terms of minimizing the average number
of jobs at the work center and completion time. This results in faster job
completion, which has the potential to generate more revenue.
Sequencing n Jobs through m Work
Centers (Line Flow scheduling)
• In Line Flow operations, we have machines arranged in
series
• A Line Flow scheduling problem can be characterized
as given below:
– A set of multiple-operation jobs is available for processing
at time zero.
– Set-up time of each job is independent of its position in
jobs sequence. So, the set-up time of each job can be
included in its processing time.
– Job descriptors are known in advance.
– There will be no interruptions in processing such as
machine breakdowns, accidents, or worker illness.
– m different machines are continuously available.
Sequencing n jobs on 2 machines
(Johnson’s rule)
• Steps in Johnson’s rule
1. List the operation time for each job in both
machines
2. Select the shortest operation time.
3. If the shortest time is for the first time, do the
job first; if it is for the second machine do the
job last.
4. Repeat step 2 and step 3 until the schedule is
completed.
Example - Johnson’s rule
• Consider the following two machines and six jobs
line flow scheduling problem. Using Johnson’s
algorithm, obtain the optimal sequence which will
minimize the makespan.
Job Machine 1 Machine 2
(minute) (minute)
A 5 4
B 2 3
C 13 14
D 10 1
E 8 9
F 12 11
Solution - Johnson’s rule
• The optimal sequence is:
BE C F AD
The makespan is determined as shown below:
Job Machine 1 Machine 2 Jobs Waiting
Time-in Time-out Time-in Time-out time
B 0 2 2 5 0
E 2 10 10 19 2
C 10 23 23 37 10
F 23 35 37 48 25
A 35 40 48 52 43
D 40 50 52 53 42
The makespan for this schedule is 53 minutes.
Total idle time on Machine 1 is 3 minutes.
Total idle time on Machine 2 is 11 minutes.
Sequencing n jobs on 2 machines
(Johnson’s rule)
• Condition to use the Johnson’s rule
– Minimum processing time on Machine 1 should be greater
than or equal to maximum processing time on Machine 2.
– Minimum processing time on Machine 3 should be greater
than or equal to maximum processing time on Machine 2.
• If any one of the above conditions is satisfied then, we
can extend Johnson’s algorithm in the following way.
– Convert the three machines problem into two machines
problem through creating hypothetical machines (say X
and Y machines)
– Processing time of X machine is Machine 1 + Machine 2
– Processing time of X machine is Machine 2 + Machine 3
Example - Johnson’s rule
• Consider the following 3 machines and 5 jobs line-
flow problem.
Job Machine 1 (hr.) Machine 2 (hr.) Machine 3 (hr.)
A 8 5 4
B 10 6 9
C 6 2 8
D 7 3 6
E 11 4 5
Solution - Johnson’s rule
Since the condition is satisfied, we can extend the Johnson’s
algorithm to this problem. So the modified problem may be
given as follows:
Job Machine X Machine Y
A 13 9
B 16 15
The optimal sequence is:
C 8 10
D 10 9
E 15 9
C B E A D
Job Machine 1 Machine 2 Machine 3 Jobs waiting
Time-in Time-out Time-in Time-out Time-in Time-out time
C 0 6 6 8 8 16 0
B 6 16 16 22 22 31 6
E 16 27 27 31 31 36 16
A 27 35 35 40 40 44 27
D 35 42 42 45 45 51 35
The makespan for this schedule is 51. Total idle time on Machine 1 is 9 hrs. Total
idle time on Machine 2 is 31 hrs. Total idle time on Machine 3 is 19 hrs.
n jobs, m machines
• Johnson’s rule can be applied if one of the
following two rules are satisfied
– Minimum processing time on machine 1 >=
maximum processing time on M2, M3,… M(m -1)
– Minimum processing time on machine m >=
maximum processing time on M2, M3,… M(m -1)
Intermittent operations Scheduling
• In an intermittent operations scheduling
problem, each job has predefined route. It is
not necessary for every job be processed on
all the work-centers.
Example
• Consider a job shop scheduling problem with four
jobs and four machines along with jobs due dates.
Represent the schedule of these jobs in the form of
Gantt Chart. Using two dispatching rules, SPT and
EDD, compare make-span, job-lateness and machine
idleness. Use smallest subscript of jobs to break ties.
Jobs Processing Requirements on machines (M) Due date
J1 M1 (8) M3 (7) M2(8) 20
J2 M3 (10) M1 (7) M2 (6) 30
J3 M1 (8) M2 (10) M3 (8) M4 (7) 40
J4 M3 (6) M4 (8) M2 (10) 50
Gantt-Chart based on a dispatching rule SPT
Gantt-Chart based on a dispatching rule EDD
Comparison of the two rules for the example
Rule Make-span
SPT 63
EDD 50
Machine Machine Idleness in SPT rule Machine Idleness in EDD rule
M1 40 27
M2 29 16
M3 32 19
M4 49 32
Jobs Jobs waiting time in SPT rule Jobs waiting time in EDD rule
J1 15 11
J2 6 17
J3 30 8
J4 0 26
Scheduling for service systems
• Service oriented organizations, such as medical
facilities, computer centers, or banks, face unique
scheduling problems.
• For some of these systems, the priority rules discussed
earlier in this section may provide sufficiently good
solutions. These approaches are useful when the
arrival of customers or jobs is random.
• When the distribution of arrivals and service times
follow a certain known dominant pattern, we can use
that information to schedule personnel and facilities.
Schedule personnel and work shift
• The objective in scheduling personnel and work and
work shifts is to minimize labor costs, given particular
service standards, or to establish some happy
compromise between labor costs and service
standards.
• The demand for the service must be forecast and
converted to equivalent labor requirements by the
hour of the day, the day of the week, and so forth.
• Scheduling is then done in relation to these
requirements. Finally, individual workers must be
assigned to work days and shifts.
Non-cyclic Personnel Schedules
• Suppose that we are faced with hourly requirements
that vary from hour to hour, day to day, week to week,
and so on.
• Staffing this operation would require continuous
adjustment to the changing requirements.
• The demand variations might be caused by trend and
seasonal factors, holidays , or weather conditions,
depending on the nature of the particular operation.
• These kinds of personnel scheduling situations can be
approached through the application of a simple
concept, the “first-hour” principle (Browne and
Tibrewala ,1975).
The first- hour principle
• The first- hour principle can be stated as
follows: assign to start to work in the first
period a number of workers equal to the
number required for that period.
• For each subsequent period, assign the exact
number of additional workers needed to meet
requirements.
• When workers come to the end of their shifts,
do not replace them if they are not needed.
Example – Non-cyclic Personnel Schedule
• Assume the following sequence of worker
requirements for the first 12 hours of a continuous
operation (once assigned workers continue working
for an 8- hour shift):
Period 1 2 3 4 5 6 7 8 9 10 11 12
Requirements, (Ri) 5 5 7 8 9 10 15 14 12 10 10 10
Solution
Period 1 2 3 4 5 6 7 8 9 10 11 12
Requirements, (Ri) 5 5 7 8 9 10 15 14 12 10 10 10
Assigned, Xi 5 - 2 1 1 1 5 - 2 - - 1
On duty, Wi 5 5 7 8 9 10 15 15 12 12 10 10
The assignment procedure would continue in the same way, in
an endless chain, as new requirements became known.
Cyclic Personnel Schedules
• Now, suppose that we have a stable situation
in which the requirement pattern repeats.
• Propp (1978) has shown that optimal solution
to cyclic staffing problems can be developed
by applying the first-hour principle
successively to the requirement schedule until
the assignment pattern repeats.
Example - Cyclic Personnel Schedules
• Assume a 24 hour operation with a 12-hour cyclic
requirements schedule where employees work
only 4 hour shifts.
Period 1 2 3 4 5 6 7 8 9 10 11 12
Requirements, (Ri) 4 6 8 8 9 7 9 7 7 7 6 5
Solution – First cycle
• Following the first hour principle, the assignments
would be as follows:
Period 1 2 3 4 5 6 7 8 9 10 11 12
Requirements, (Ri) 4 6 8 8 9 7 9 7 7 7 6 5
Assigned, Xi 4 2 2 - 5 - 4 - 3 - 3 -
On duty, Wi 4 6 8 8 9 7 9 9 7 7 6 6
Solution – Second cycle
Period 1 2 3 4 5 6 7 8 9 10 11 12
Requirements, (Ri) 4 6 8 8 9 7 9 7 7 7 6 5
Assigned, Xi 1 2 5 - 2 - 7 - - - 6 -
On duty, Wi 4 6 8 8 9 7 9 9 7 7 6 6
Solution – Third cycle
Period 1 2 3 4 5 6 7 8 9 10 11 12
Requirements, (Ri) 4 6 8 8 9 7 9 7 7 7 6 5
Assigned, Xi - - 8 - 1 - 8 - - - 6 -
On duty, Wi 6 6 8 8 9 9 9 9 8 8 6 6
Solution – Fourth cycle
Period 1 2 3 4 5 6 7 8 9 10 11 12
Requirements, (Ri) 4 6 8 8 9 7 9 7 7 7 6 5
Assigned, Xi - - 8 - 1 - 8 - - - 6 -
On duty, Wi 6 6 8 8 9 9 9 9 8 8 6 6
The assignment and the workers on duty for the third and fourth cycles are identical;
they would continue to repeat with additional cycles, and they are optimal. The
staffing pattern shown in the third and fourth cycles should be applied repetitively as
long as the requirements pattern remains stable. The resulting slack of 9 worker-
hours in the resources applied is shown in the bottom row of the fourth cycle. The
sum of the requirements over the 12-hour period is 83 worker-hours, and 83 + 9 =
92 worker hours were used.
Weekly schedules for Seven-day
operations
• Many services and some manufacturing
operations must operate on a seven days per
week basis, employing labor that normally
works approximately 40 hours per week.
• One of the simplest constraints is that each
worker must be provided with two
consecutive days off each week.
• A computerized algorithm for this problem
was developed by Browne (1979, 1980)
Steps - Days off personnel schedule
1. Determine the necessary daily staffing requirement
2. Identify the two consecutive days that the lowest total
requirement and circle these. Assign these two days off to the first
employee. In the case of tie, choose the day with the lowest
adjacent requirement, or by first assigning Saturday and Sunday as
an “off” day. If there are more than, make an arbitrary decision.
3. Make a new row for the next employee by subtracting 1 from the
first row except for the circled day and any day that has a value of
zero.
4. In the next raw, identify the two consecutive days that have the
lowest total requirement and circle them. Assign the next
employee to the remaining days.
5. Repeat the process (steps 3 and 4) until all the requirements are
met
Example – Days off personnel schedule
• A Hospital administrator wants to staff the oncology ward
using a standard 5 – day work-week with two consecutive
days off, but also wants to minimize the staff. However, as
in most hospitals, she faces an inconsistent demand.
Weekends have low usage. Doctors tend to work early in
the week, and patient’s peak on Wednesday then taper off.
Day Monday Tuesday Wednesday Thursday Friday Saturday Sunday
Staff
required 5 5 6 5 4 3 3
Solution
The administrator needs six full – time employees to meet the staffing needs
and one employee to work Saturday.
References
• Elwood S. Buffa, and Rakesh K. Sarin (1987).
Modern production and operations management,
Eighth Edition.
• Heizer J. and Render B., (2011). Principles of
Operations Management, tenth edition Pearson
Prentice Hall.
• R. Panneerselvam. (2012), Production and
Operations management, Third edition.
• Stevenson, William J., 2012, Operations
Management, eleven Edition, McGraw-Hill
Ryerson Ltd.
