Operations Scheduling and Sequencing

15-1 Understanding Scheduling and Sequencing

Scheduling: Assigning start and completion times to jobs, people, or equipment.
Sequencing: Determining the order in which jobs or tasks are processed.
Scheduling and sequencing applies to all aspects of a value chain, including:
- Planning and releasing orders in a factory.
- Determining work shifts for employees.
- Routing vehicles and making deliveries to customers.
- Scheduling patient visits and surgeries.

15-1a Production Scheduling in Manufacturing

Production scheduling involves managing and controlling a production process to satisfy product delivery and efficiently utilize manufacturing resources.
Schedules are evaluated using:
- Shop performance: Focuses on machine utilization and work-in-process inventory. Common measures include makespan and flow time.
- Due dates: Reflect promised delivery dates to customers and are vital to achieving customer satisfaction. Common measures include tardiness and lateness.

15-1b Production Scheduling in Service Organizations

Scheduling techniques used in manufacturing transfer well to low-contact (back room) service systems.
High-contact (front room) service systems are more difficult to schedule because customer participation affects customer demand, arrival times, and service times.
In service systems without physical inventory, the capability to process customers depends solely on the system's capacity.

15-2 Staff Scheduling

Staff scheduling matches available personnel with organizational needs by:
1. Accurately forecasting demand and translating it into work quantity and timing.
2. Determining staffing required to perform the work by time period.
3. Determining personnel available and the full- and part-time mix.
4. Matching capacity to demand and developing a schedule that maximizes service and minimizes costs.
Staff scheduling problems can be addressed using commercial software or optimization models.

15-2a Scheduling Consecutive Days Off

Scheduling staff for consecutive days off involves:
1. Listing the minimum number of employees required for each day.
2. Locating at least two consecutive days with the smallest requirements.
3. Circling the requirements for those two days.
4. Assigning employee 1 to work on all non-circled days and subtracting 1 from the requirement for each day worked.
5. Repeating the process until all requirements become zero.

15-2b Optimization Models for Staff Scheduling

Common problems in staff scheduling:
1. Determining the number of employees needed per shift to meet hourly requirements while minimizing the total number of employees (integer optimization problem).
2. Assigning staff to jobs, projects, or events (assignment model).

15-2c Appointment Systems

Appointments are reservations of service time and capacity that:
- Maximize the use of time-dependent service capacity.
- Reduce service costs and no-show risks.
- Accommodate customers and forecast their behavior.
Four decisions in designing an appointment system:
1. Determine the appointment time interval.
2. Determine the length of each workday and time off duty.
3. Decide how to handle overbooking.
4. Develop customer appointment rules to maximize customer satisfaction.

15-3a Sequencing Performing Criteria

Three performing criteria for sequencing jobs on a single processor:
1. Process-focused performance:
  - Data about job start and end times.
  - Focuses on shop performance like equipment utilization and WIP inventory.
2. Customer-focused due date:
  - Customers' required due dates or internally determined shipping dates.
3. Cost-based:
  - Considered implicitly in process performance and due-date criteria.

15-3a Performance Measure: Flow Time

Flow time is the time a job spends in the shop or factory. Low flow times reduce WIP inventory.
Flow time formula: $Fi = Si + P_i$ , where
- $F_i$ = flow time of job i
- $S_i$ = start time of job i
- $P_i$ = processing time of job i

15-3a Performance Measure: Makespan

Makespan is the time needed to process a given set of jobs. A short makespan aims to achieve high equipment utilization.
Makespan formula: $M = Cn - S1$ , where
- $M$ = makespan of a group of jobs
- $C_n$ = completion time of the last job in the group
- $S_1$ = start time of the first job in the group

15-3a Due-Date Measures

Lateness is the difference between the completion time and the due date (positive or negative): $Li = Ci - D_i$
Tardiness is the amount of time by which the completion time exceeds the due date: $Ti = Max(0, Li)$ , where
- $L_i$ = lateness of job i
- $D_i$ = due date of job i
- $T_i$ = tardiness of job i

15-3b Three Popular Sequencing Rules

First come, first served (FCFS): Prioritizes jobs arriving intermittently. Used in service-delivery systems, focuses only on arrival time.
Shortest processing time (SPT): Prioritizes jobs in the short term. Minimizes average flow time and WIP inventory and maximizes resource utilization.
Earliest due date (EDD): Prioritizes jobs in the short term. Minimizes the maximum of jobs past the due date but is not suitable for average flow time, WIP inventory, or resource utilization.

15-3c An Excel Template for Sequencing

Sequencing template is available to evaluate sequencing rules for a single processor.
Input: processing times, due dates, and sequences for up to 10 jobs.
Output: average flowtime, lateness and tardiness, the number of tardy jobs, and maximum tardiness.

15-4 Dispatching Rules for Job Shop Scheduling

For real-life scheduling problems in job shops, use simple rules of thumb.
Dispatching is selecting jobs for processing and authorizing the work.
In manufacturing, dispatching is part of “shop floor control.”
In service systems, dispatching occurs in the front or back offices.
Typical priority dispatching rules include:
- Fewest number of operations remaining (FNO).
- Least work remaining (LWR)—the sum of all processing times for operations not yet performed.

Solution 15.9: Using the NFO Dispatching Rule

$t = 0$ , job 1 is immediately scheduled on L and moved to D at $t = 10$ . $t = 15$ , job 2 arrives; $t = 20$ , job 3 arrives; both wait for job 1 on D.
$t = 30$ , job 1 finishes on D and moves to G. Job 3 is scheduled first on D because it has only two operations remaining, whereas job 2 has four (NFO dispatching rule).

15-5 Two-Resource Sequencing: Johnson’s Rule

Consider a two-resource flow shop where each job is processed first on Resource #1, then on Resource #2.
Johnson’s Rule (1954) finds a minimum makespan schedule:
1. List the jobs and their processing times on Resources #1 and #2.
2. Find the job with the shortest processing time (on either resource).
3. If the time corresponds to Resource #1, sequence the job first; if it corresponds to Resource #2, sequence the job last.
4. Repeat steps 2-3 until all jobs are scheduled.

Solution 15.10: Applying Johnson’s Rule

The solution details the step-by-step application of Johnson's Rule to a specific problem, showing how the job sequence is determined based on processing times on two resources.

Analysis 15.10: Applying Johnson’s Rule

Johnson’s rule is a powerful algorithm when the sequencing problem structure fits the assumptions.
Compared to the original sequence:
- Makespan is reduced from 37 to 27 days.
- Average flow time improved from 22.4 to 18.2 days.
- Total idle time on the punch press is now only four days.
- Punch press resource utilization improved to $\frac{23}{27} = 85.2\%$ .

15-6 Schedule Monitoring and Control

Schedule monitoring and control are necessary for rapidly changing scheduling environments.
Bar charts help monitor planned schedules and track jobs' progress.

15-7 Vehicle Routing and Scheduling

A common problem in logistics is determining routes from a central depot to delivery sites.
Minimizing total delivery time or distance reduces operating costs and emissions.
The number of possible routes increases quickly, making complete enumeration impractical.
Linear optimization or heuristic methods can be used to find good route plans.

15-7 A Heuristic Procedure for Vehicle Routing

The Clarke-Wright Method:
1. Assumes each customer is being serviced individually from the depot.
2. Combines customers into longer routes to reduce travel time within capacity restrictions.
The savings associated with combining two routes is: $S(i,j) = d(0,i) + d(0,j) - d(i,j)$

15-7 The Clarke-Wright Method

The Clarke-Wright Method is implemented as follows:
1. Compute the savings $S(i,j)$ for all pairs of customers i and j.
2. Find the pair with the largest positive savings and determine if there is sufficient capacity to link them. Construct a new route if possible, otherwise, try the next largest savings.
3. Continue applying step 2 as long as the next largest savings is positive. Stop when all positive savings have been considered.

Solution 15.11: Applying the Clarke-Wright Method

Demonstrates the application of the Clarke-Wright Method with a step-by-step calculation of savings and route combination to reduce total travel time, subject to capacity constraints.
Combining routes (1,2) and (3,5), decreased total travel time from 452 to 261 minutes. No further route combination is possible, given the capacity constraint of 80 cases.

Check Your Knowledge 15.1

A production schedule describes all of the following EXCEPT: the amount of available resources.
Staff scheduling attempts to match available personnel with the needs of the organization by: determining the staffing required to perform the work by time period.

Check Your Knowledge 15.2

Sequencing is necessary when several activities use a common resource.
Which of the following statements about Johnson's rule of sequencing is true? It can be used to sequence jobs in a two-resource sequencing problem.