Instructor’s Manual – OMSC2 – Collier/Evans – C15 Operations Scheduling and Sequencing
This chapter introduces students to scheduling and sequencing and describes approaches for
staff scheduling, sequencing on as single processor, two-resource sequencing problems,
dispatching, using Gantt charts to monitor schedules, and the Clarke-Wright method for vehicle
routing and scheduling.
Questions and problems are provided in four categories:
1. Review questions
2. Discussion questions and experiential activities
The chapter has three cases:
1. Luke’s Balloon Shop is the first case study. It focuses on sequencing jobs on a single
2. The second case, Midwest Frequent Flyer Call Center, requires students to evaluate demand
3. The integrative case study, Hudson Jewelers, with case assignment questions in all chapters,
KEY TERMS
Dispatching is the process of selecting jobs for processing and authorizing the work to be done.
2
positive or negative).
Makespan is the time needed to process a given set of jobs.
REVIEW QUESTIONS
1. Define scheduling and sequencing. Provide examples from your experiences.
Scheduling refers to the assignment of start and completion times to particular jobs, people,
or equipment. Scheduling incorporates start and completion times such as work shift
2. Explain how scheduling affects customer service and costs. Provide an example.
Good schedules and sequences lead to efficient execution of manufacturing and service
plans. The help to minimize customer and material waiting and delays, thus reducing costs
3. What are the four major decisions made by staff scheduling?
• accurately forecasting demand and translating it into the quantity and timing of work to
be done,
3
4. Why are appointment systems used? What decisions are necessary to design an
appointment system?
Service capacity is perishable and appointment systems improve resource utilizations and
5. Describe some practical examples of the single-resource sequencing problem.
The simplest sequencing problem is that of processing a set of jobs on a single processor.
This situation occurs in many firms. For example, in a serial manufacturing process, a
6. Define flow time, makespan, tardiness, and lateness, and explain how they are computed.
Flow time is the amount of time a job spent in the shop or factory. Low flow times reduce
WIP inventory. Flow time is computed using Equation 14.1.
Fi = Si + Pi [14.1]
where
4
Lateness is the difference between the completion time and the due date (either positive or
negative). Tardiness is the amount of time by which the completion time exceeds the due
7. What are the advantages and disadvantages of the SPT and EDD sequencing rules?
The SPT sequencing rule maximizes workstation utilization and minimizes average job flow
time and work-in-process inventory. This is a very powerful sequencing rule. One
8. What is dispatching? Explain how priority dispatching rules are used.
Dispatching is the process of selecting jobs for processing and authorizing the work to be
done. When new jobs arrive in an intermittent fashion, resulting in a constantly changing
mix of jobs needing to be sequenced, dispatching rules assign priorities to whatever jobs
9. Summarize the procedure (steps) used for the two-resource sequencing problem
(Johnson’s Sequencing Rule).
5
S. M. Johnson developed the following algorithm in 1954 for finding a minimum makespan
schedule. The following algorithm (procedure) defines Johnson’s Sequencing Rule for the
two-resource problem structure.
1. List the jobs and their processing times on Resources #1 and #2.
10. What is a Gantt chart and why is it important?
This schedule for the two-resource sequencing problem can be represented by a simple
11. Why must schedules be closely monitored and often revised?
Murphy’s Law states that if something can go wrong it will, and this is especially true with
schedules. And demand can change, machines break down, inventory counts are updated,
12. What are the objectives of vehicle routing and scheduling?
Typical objectives are to minimize total delivery time or distance travelled, reduce
DISCUSSION QUESTIONS AND EXPERIENTIAL ACTIVITIES
13. Discuss how you decide to schedule your school assignments. Do your informal scheduling
rules correspond to any of those in this chapter?
Many students will probably recognize that they use a shortest processing time
(procrastination!) rule, or an earliest due date to establish priorities, even though they
14. How does your college or university schedule classes? What criteria are used?
This is a complex problem that involves student demand, prerequisites, classroom
15. Discuss scheduling and sequencing issues in municipal services such as garbage collection,
school-bus routing, or snowplowing. What types of criteria and approaches might be used?
These are complex scheduling problems in that numerous alternative routes exist. For
16. Interview an operations or logistics manager at a nearby manufacturing or service company
to find out about scheduling problems the company faces and how they are addressed.
This question can help make the text material relevant and also demonstrate to the
17. Write one-page paper listing the advantages and disadvantages of using part-time
employees to help meet demand.
The main advantage of part-time employees is to help minimize cost. Other advantages
include flexibility, screen and on-the-job training of potential full-time employees, and
7
18. Explain why appointments are necessary for many professional services. (Hint: How do
services differ from goods as described in Chapter 1?) List and explain some key issues and
decisions that must be addressed in designing appointment systems.
Seven differences between goods and services are described in Chapter 1. You might begin
19. Why is staff scheduling in a service environment a difficult task? What can managers do to
ensure that staff schedules are effective and efficient?
Question #5 provides background on this question. Staff scheduling can be divided into
routine service organizations (RSOs) and professional service organizations (PSOs.) RSOs
include banks, hotels, airlines, distribution centers, and retail stores. PSOs include doctor’s
20. Research software available to organizations to create staff schedules. What features do
these types of software have? Prepare a one-page report.
A Google search of “staff scheduling” will provide many examples. One website,
8
21. Explain how modern vehicle routing and dispatching software and systems can support
sustainability goals and objectives.
The simple answer is we use fewer resources to accomplish more work. The resources are
normally labor such as the number of postal delivery workers or equipment such as
delivery trucks. Fewer resources used means less CO2 in the atmosphere and less
22. Do an Internet search of “vehicle-routing software” and “vehicle routing.” Write a two–
page report of the capabilities, advantages, and disadvantages of these vehicle-routing and
dispatching systems. Provide one or two examples of real-world applications of these
systems and the benefits.
A Google search reveals several million hits for “vehicle routing software” so your students
have plenty of information to build a short paper upon. Numerous firms provide
9
COMPUTATIONAL PROBLEMS AND EXERCISES
These exercises require you to apply the formulas and methods described in the chapter. The
problems should be solved manually.
23. A hospital emergency room needs the following numbers of nurses.
Each nurse should have two consecutive days off. How many full-time nurses are required,
and what is a good nurse schedule?
Notice this is a difficult target-staffing pattern ranging from a minimum of 4 to 8 nurses. There
10
24. A supermarket has the following minimum personnel requirements during the week. Each
employee is required to have two consecutive days off. How many regular employees are
required, and what is a good schedule?
25. Five jobs are to be processed on one machine. If the jobs are processed in the FCFS order
1-2-3-4-5, compute the start time and flow time for each job.
Job Sequence (i) Start Time (Si) Processing Time (Pi) Flow Time (Si + Pi)
1 0 8 0 + 8 = 8 hours
26. These six jobs are to be scheduled on a single machine:
11
a. Suppose the jobs are processed in FCFS numerical order. Compute the makespan, flow
time for each job, and overall average flow time.
Job Sequence (i) Start Time (Si) Processing Time (Pi) Flow Time (Si + Pi)
1 0 100 0 + 100 = 100 min.
2 100 130 100 + 130 = 230 min.
b. In what order would the jobs be processed using the SPT rule? Compute the average
flowtime after each job is completed. Compare this answer with your answer to part a.
Job Sequence (i) Start Time (Si) Processing Time (Pi) Flow Time (Si + Pi)
6 0 80 0 + 80 = 80 min.
27. On Tuesday morning at 8 a.m., an IT analyst found four project “tickets” in her inbox that
arrived overnight. The estimated times to complete the projects and the due dates
requested are given below. If the projects are processed in a FCFS order (1-2-3-4),
compute the flow time, lateness, and tardiness for each project.
28. Five patients arrived at the radiology department in a hospital and are waiting for X-rays.
Use the SPT rule to create a schedule. Compute the start time and flow time for each patient.
Job Sequence (i) Start Time (Si) Processing Time (Pi) Flow Time (Si + Pi)
5 0 15 0 + 15 = 15 min.
29. A workstation has one maintenance mechanic to repair failed machines. We can think of
the mechanic as the processor (scarce resource) and the machines awaiting repair as the
jobs. Let us assume that six machines are down, with estimated repair times given here,
and that no new machines fail.
Compute the flow time for each job using both the FCFS rule and the SPT rule, and
13
30. Five customers brought in computers to be repaired to a small shop. Estimated repair
times (in days) and dates promised are given below. Due dates were set based on
available technicians; however, one technician had a medical emergency and will be
unavailable for at least two weeks, so processing times were adjusted.
31. At Lynwood Manufacturing, (see Solved Problem 15.9), suppose the dispatcher uses the
least work remaining rule (LWR) instead of FNO. Which job (job 2 or job 3) will be
scheduled next on the drill press at time 30?
If the LWR (least work remaining) rule is chosen, then we see that job 2 has 90 minutes of
32. A manufacturing process involving machined components consists of two operations done
on two different machines. The status of the queue at the beginning of a particular week is
as follows:
14
Because this is a two-machine flow shop problem, Johnson’s rule is applicable. Total time
in minutes on each machine is the product of the number of components and the unit
times, as shown here.
Job Machine 1 Machine 2
101 500 500
The sequence specified by Johnson’s rule is 201-213-184-101-185-176. The schedules are
shown in the following two different versions of Gantt charts.
33. On Monday morning, Baxter Industries has the following jobs waiting for processing in two
departments, milling and drilling, in that order.
15
a. Develop a minimum makespan schedule using Johnson’s rule.
Sequence the jobs in the following order: 617, 216, 519, 327, 258, 462
b. Construct a Gantt chart for the minimum makespan schedule.
time: 0 2 9 16 22 32 44 47
|—|-—-—-|–—-|–——-|——-|———-|-——-|
job: 617 216 519 327 258 462
Makespan = 47 hours (notice that when all jobs finish on the mill, they can immediately begin
on the drill. The drill is only idle for 2 hours waiting for the first job.
34. Dan’s Auto Detailing business performs two major activities: exterior cleanup, and interior
detailing. Based on the size of car and condition, time estimates for six cars on Monday
morning are as shown in the accompanying table.
a. Sequence the cars so that all exterior detailing is done first and total completion time is
minimized.
b. Draw a Gantt chart and evaluate the idle time.
16
Job Exterior Interior
—– ———— ———
1 50 30
2 35 40
The shortest processing time is for Job 3 at 20 so it is scheduled last. The next shortest is
job 5 at 25 minutes so it is next to last. The next shortest time is 30 for Job 1 so it is
b. Draw a Gantt chart and evaluate the idle time.
The schedules are shown on the following Gantt charts (timelines are not to scale)
Exterior:
0 35 115 180 230 275 365
Interior (dash single lines are idle time and asterisks are job processing times (2 – 6 – 4 – 1 – 5 – 3)
Time –—-35***75-—115****170–-180***225-230*** 260—275**300-——365**385
The idle time adds up to 170 minutes (35+40 + 10 + 5 + 15 + 65) while the actual processing
35. The Naples Newspaper completes production of its daily edition by 5 a.m. A truck picks up
pallets loaded with newspapers and delivers them to five neighbor sites, where carriers
sort and fold the papers for individual routes. The mileage is shown in the following table.
Currently, the truck picks up the number of pallets required by each customer at the
factory, delivers them, and then returns to the factory to get the papers for the next
17
a. How many miles does the truck travel each day using the current route? What is the
total number of miles traveled annually?
The current route is 0-1-0-2-0-3-0-4-0. The number of miles per day is
b. Use the Clarke-Wright Method to find a more efficient route.
Delivery Distance Demand
i/j 0 1 2 3 4 (Pallets required)
0 – 20 11 4 7 –
We compute the savings between each pair of customers s(i,j) as follows:
s(1,2) = t(0,1) + t(0,2) – t(1,2) = 20 + 11 – 10 = 31
The savings in miles are summarized in the table below:
i/j 1 2 3 4
18
The initial solution is to service all customers from the factory:
Routes Travel Distance Pallets on route Capacity available
0-1-0 40 10 16 – 10 = 6
The largest savings is 31 for sites 1 and 2. If these sites are combined on the same
New solution:
Routes Travel distance Cases on route Capacity available
0-1-2-0 31 16 16 – 16 = 0
0-3-0 8 4 16 – 4 = 12
0-4-0 14 8 16 – 8 = 8
Total: 53
Note that the total travel distance was reduced by the amount of the savings (84 – 53 = 31).
The next largest savings is 19, between customers 1 and 3. However, if we add
customer 3 on the route 0-1-2-0, the total pallets for this site (3) would exceed the
c. How many miles, gallons, and dollars can be saved per year by adopting the current
versus shorter route found by the Clarke-Wright Method?
53*365 = 19,345 miles per year for this shorter C-W heuristic method route
d. How many pounds of gas are emitted into the atmosphere and saved per year using
the shortest truck route versus the current truck route? Assume that one gallon of gas
19
Extra Insights Not Assigned in the problem in case a student asks
Departing from the C-W heuristic solution shown in (a) to (c) consider the following addition to
the C-W heuristic solution.
Note that if we decide to combine customers 3 and 4 based on intuitive logic, not the C-W
heuristic logic, the total distance is 56:
Routes Travel distance Pallets on route Capacity available
0-1-2-0 31 16 16 – 16 = 0
Here, one truck makes one trip back to the factory to serve four customers, two customers
on each route for a total of two round trips. Or one could assume that two trucks are used,
EXCEL-BASED PROBLEMS
For these problems, you may use Excel Solver or the spreadsheet templates in MindTap to assist
in your analysis.
36. For the scenario described in section 15.2c, suppose the number of employees needed for
each hour are as shown in the following table:
20
Develop and solve the optimization model on a spreadsheet and use Solver to find the
number of employees to assign to the four work shifts to minimize the total number of
employees.
The Excel model (with the optimal solution), formulas, and Solver model (available on the
Instructor site) are shown below.