Topic 10. Scheduling

TOPIC 10:
SCHEDULING
KỸ THUẬT ĐIỀU ĐỘ
Dr. Le Thi Diem Chau
Dept. of Industrial & Systems Engineering
Faculty of Mechanical Engineering
Email: [email protected]
Scheduling
§ Thiết lập thời gian sử dụng thiết bị, cơ sở vật chất và hoạt động
con người trong một tổ chức (Establishing the timing of the use
of equipment, facilities, and human activities in an organization)
§ Là một quá trình ra quyết định:
§ Chỉ ra :
• cái gì sẽ được làm,
• khi nào,
• bởi ai
• công cụ/máy móc nào
§ Đảm bảo đúng tiến độ theo lịch sản xuất + giải quyết hài hòa
mối quan hệ các mục tiêu
Scheduling
Scheduling
Scheduling
Scheduling
§ The objective of scheduling:
• is to allocate and prioritize demand to available facilities
• demand generated by either forecasts or customer orders
§ Three factors are pervasive in scheduling:
• generating the schedule forward or backward
• finite and infinite loading
• the criteria (priorities) for sequencing jobs
Forward and Backward
Scheduling
§ Forward scheduling starts the
schedule as soon as the job requirements
are known
§ EX: hospitals, clinics, restaurants, and machine tool

manufacturers
Forward and Backward
Scheduling
§ Backward scheduling begins
with the due date, scheduling the final
operation first
§ EX: catering a banquet or scheduling surgery

Finite and Infinite Loading
Loading is the process of assigning jobs to work stations or

processes.
§ Finite loading:
• load (or assign) work only up to the capacity of the process
§ Infinite loading:
• load work without regard for the capacity of the process
Scheduling Criteria
1. Minimize completion time:
• By determining the average completion time
2. Maximize utilization:
• By determining the percent of the time the facility is utilized
3. Minimize work-in-process (WIP) inventory:
• By determining the average number of jobs in the system
4. Minimize customer waiting time:
• By determining the average number of late periods (e.g.,
days or hours)
Different processes require
different schedules
v Process-focused facilities (Job shop)
§ Scheduling to customer orders where changes in both
volume and variety frequently
§ Schedules are often due-date focused, with loading
refined by finite loading techniques
EX: foundries, machine shops, cabinet shops, print shops,

many restaurants, and the fashion industry
different schedules
v Repetitive facilities (assembly lines)
§ Schedule production and assembly based on frequent
forecasts
§ Finite loading with a focus on generating a forward-
looking schedule
§ JIT techniques are used to schedule components that
feed the assembly line
EX: assembly lines for washing machines at Whirlpool and

automobiles at Ford
different schedules
v Product-focused facilities (continuous)
§ Schedule high-volume, limited-variety products to meet
stable demand within existing fixed capacity
§ Finite loading generates schedules based on setup and
run times for limited products
EX: huge paper machines at International Paper, beer in a

brewery at Anheuser-Bush
Focus on….
v Scheduling Process-Focused Facilities
q Loading jobs
q Sequencing jobs
Loading Jobs
§ is oriented to capacity:
• via a technique known as input–output control
• two approaches used for loading:
+ Gantt charts
+ the assignment method of linear programming
§ is related to assigning specific jobs to work centers
12
Input–Output Control
§ Allows operations personnel to manage facility work flows
Gantt Charts
§ Planning charts used to schedule resources and allocate time
12
Gantt scheduling chart: EX
First printing in Winter Park, Florida, wants to use a Gantt chart to
show the scheduling of three orders, jobs A, B, and C
Assignment Method
§ Involves assigning tasks or jobs to resources
§ A special class of linear programming models
§ To minimize total costs or time required to perform the

tasks at hand
§ Important: only one job (or worker) is assigned to one

machine (or project).
Assignment Method
1. Determine zero opportunity costs:
§ Subtract the smallest number in each row, then
subtract the smallest number in each column
2. an optimal assignment or not:

§ Draw the minimum number of vertical and horizontal
lines to cover all zeros.
§ If the lines equal the number of rows or columns,
make an optimal assignment (see Step 4).
§ If fewer, proceed to Step 3
Assignment Method
3. Step 3:
§ Subtract the smallest uncovered number from all
uncovered numbers.
§ Add it to numbers at the intersection of two lines.
§ Leave numbers covered by one line unchanged.
§ Return to Step 2 and continue until an optimal
assignment is possible
Assignment Method
3. Step 4:
§ Optimal assignments are always at zero locations
§ Prioritively select a row or column with only one
zero, assign it, and draw lines through its row and
column.
§ Repeat this process with the remaining rows and
columns until all tasks are assigned
Assignment Method: EX
First Printing has three available typesetters (A, B, and C)
and three new jobs to be completed. Assign jobs to machines
Step 1:
1A. Subtract the smallest number in each row from every number
in the row
Step 1:
1B. Subtract the smallest number in each column from every
number in the column
Step 2:
Draw the minimum number of vertical and horizontal lines to
cover all zeros
Step 3: Subtrast the smallest uncovered number from every other
uncovered number and add it to numbers at the intersection of
two lines
Return to step 2: Cover the zeros with straight lines again
Ø Assign R-34 to person C, S-66 to person B, and T-50 to person A

q Minimum cost = $6 + $10 + $9 = $25
§ If assign S-66 to A, could not assign T-50 to a zero location
§ If costs $10 for C to complete job R-34 instead of $6
q R-34 to A, S-66 to B, T-50 to C  cost = $28
Sequencing Jobs
q Sequencing
§ Determining the order in which jobs should be done at each
work center
q Priority rules
§ Determine the sequence of jobs in processoriented facilities
q Flow time
§ The time between the release of a job to a work center until
the job is finished
EX: if Job B waits 6 days for Job A to be processed and then takes 2
more days of operation time itself, its flow time: 6 + 2 = 8 days
Priority rules
q FCFS: first come, first served
§ Jobs are completed in the order they arrived
q SPT: shortest processing time
§ Jobs with the shortest processing times are assigned first
q EDD: earliest due date
§ Earliest due date jobs are assigned first.
q LPT: longest processing time
§ Jobs with the longest processing time are assigned first
Performance Criteria
vThe priority rules try to:
§ minimize completion time
§ maximize facility utilization
§ minimize number of jobs in the system
§ minimize job lateness
q Performance criteria incorporate the concept of flow time

Performance Criteria Measurement
Job lateness = Max {0, yesterday + flow time – due date}
q Assumption:
§ today is a work day, work has not yet begun today, and
§ a job finished by the end of a day can be delivered to the

customer that same day
For example. Today is day 20 (thus yesterday was day 19).

Job A is due tomorrow (day 21) and has a flow time of 1 day. That
job would be considered to be completed on time, i.e., not late:
Max {0, 19 + 1 – 21} = Max {0, -1} = 0 days late
Job B is due on day 32 and has a flow time of 15 days:
Max {0, 19 + 15 – 32} = Max {0, 2} = 2 days late

Critical Ratio
A sequencing rule that is an index number computed by
dividing the time remaining until due date by the work time
remaining
The critical ratio gives priority to jobs that must be done to
keep shipping on schedule. A job with a low critical ratio
(less than 1.0) is one that is falling behind schedule. If CR is
exactly 1.0, the job is on schedule. A CR greater than 1.0
means the job is ahead of schedule and has some slack
12
Critical Ratio: EX
Today is day 25 on Zyco Medical Testing Laboratories'
production schedule
12
Critical Ratio: EX
Today is day 25 on Zyco Medical Testing Laboratories' production schedule
Job B has a critical ratio of less than 1, meaning it will be late unless
expedited => it has the hightest priority
Job C is on time, and job A has some slack
Once job B has been completed, we would recompute the critical ratios for
jobs A and C to determine whether thier priorities have changed
12
Critical Ratio
In most production scheduling systems, the critical-ratio rule can help do
the following:
1. Determine the status of a specific job.
2. Establish relative priority among jobs on a common basis.
3. Adjust priorities (and revise schedules) automatically for changes in
both demand and job progress.
4. Dynamically track job progress.
12
Sequencing N Jobs on Two
Machines: Johnson’s Rule
Johnson’s rule. An approach that minimizes the total
time for sequencing a group of jobs through two work
centers while minimizing total idle time in the work centers
12
Sequencing N Jobs on Two
Machines: Johnson’s Rule
v Johnson’s rule involves four steps:
§ All jobs are to be listed, and the time that each requires on a
machine is to be shown.
§ Select the job with the shortest activity time. If the shortest
time lies with the first machine, the job is scheduled first. If
the shortest time lies with the second machine, schedule the
job last. Ties in activity times can be broken arbitrarily.
§ Once a job is scheduled, eliminate it.
§ Apply steps 2 and 3 to the remaining jobs, working toward
the center of the sequence
12
Johnson's Rule
Five specialty jobs at a La Crosse, Wisconsin, tool and die
shop must be processed through two work centers (drill
press and lathe). The time for processing each job follows:
The owner, Niranjan Pati, wants to set the sequence to

minimize his total time for the five jobs
Johnson's Rule
Johnson's Rule
• The second work center will wait 3 hours for its first job, and it will also wait 1 hour
after completing job B
• If job C takes 8 hours in work center 2 (instead of 4 hours), what sequence is best?
[ B-E-C-D-A]
Limitations of Rule-Based
Sequencing Systems
1. Scheduling is dynamic; therefore, rules need to be revised to
adjust to changes in orders, process, equipment, product
mix, and so forth
2. Rules do not look upstream or downstream; idle resources
and bottleneck resources in other departments may not be
recognized.
3. Rules do not look beyond due dates. For instance, two
orders may have the same due date. One order involves
restocking a distributor and the other is a custom order that
will shut down the customer’s factory if not completed.
Both may have the same due date, but clearly the custom
order is more important
12

Topic 10. Scheduling

Uploaded by

Copyright:

Available Formats

Topic 10. Scheduling

Uploaded by

Document Information

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

Topic 10. Scheduling

Uploaded by

Copyright:

Available Formats

TOPIC 10:

§ EX: hospitals, clinics, restaurants, and machine tool

§ EX: catering a banquet or scheduling surgery

Loading is the process of assigning jobs to work stations or

EX: foundries, machine shops, cabinet shops, print shops,

EX: assembly lines for washing machines at Whirlpool and

EX: huge paper machines at International Paper, beer in a

• two approaches used for loading:

+ the assignment method of linear programming

§ is related to assigning specific jobs to work centers

§ A special class of linear programming models

§ To minimize total costs or time required to perform the

§ Important: only one job (or worker) is assigned to one

2. an optimal assignment or not:

Ø Assign R-34 to person C, S-66 to person B, and T-50 to person A

§ minimize completion time

§ maximize facility utilization

§ minimize number of jobs in the system

§ minimize job lateness

q Performance criteria incorporate the concept of flow time

§ a job finished by the end of a day can be delivered to the

For example. Today is day 20 (thus yesterday was day 19).

Max {0, 19 + 1 – 21} = Max {0, -1} = 0 days late

Job B is due on day 32 and has a flow time of 15 days:

Max {0, 19 + 15 – 32} = Max {0, 2} = 2 days late

The owner, Niranjan Pati, wants to set the sequence to

You might also like