Understanding Setup Times in Flow Shop Scheduling

Flow shop scheduling is a core challenge in manufacturing, where multiple jobs must be processed on a series of machines in the same order. The objective is to find a sequence that minimizes the total completion time, known as the makespan, or other performance metrics. Among the many variables that influence optimal scheduling, setup times stand out as a critical yet often underestimated factor.

Setup time refers to the period required to prepare a machine for processing a new job. This includes activities such as changing cutting tools, reconfiguring jigs and fixtures, loading new programs, cleaning residues, and adjusting temperature or pressure settings. In some industries, setup times can account for up to 30% of total production time, making their management essential for efficiency.

Types of Setup Times

Setup times can be classified based on their dependency on job sequence. Sequence-independent setup times are constant for a given job regardless of the previous job. For example, cleaning a mixer after any batch may take the same time. In contrast, sequence-dependent setup times vary depending on the order of jobs. Changing from a light color to a dark color on a printing press may require less cleaning than the reverse. Sequence-dependent setups are more challenging to model and optimize, but they reflect real-world conditions in many manufacturing environments.

Measuring Setup Times

Accurate measurement is the first step toward improvement. Companies use time-and-motion studies, automated data capture from machine controllers, and manual observation to record setup durations. These measurements feed into scheduling algorithms and help identify bottlenecks. Common metrics include average setup time per job, setup time as a percentage of total processing time, and the ratio of internal (performed while machine is stopped) to external (performed while machine is running) setup activities.

The Impact of Setup Times on Scheduling Efficiency

Ignoring setup times in flow shop scheduling can lead to suboptimal sequences that increase idle time, lengthen makespan, and raise costs. When setups are long, the scheduler must balance the trade-off between grouping similar jobs to reduce setups and meeting due dates for different customers.

Effects on Throughput and Makespan

In a flow shop, the makespan is the time from the start of the first job to the completion of the last job on the last machine. High setup times inflate the makespan directly. Moreover, if setups are sequence-dependent, an inefficient sequence can cause a cascade of delays. For instance, a job requiring a lengthy setup on the first machine will push back all subsequent jobs on that machine, potentially idling downstream machines. Studies show that neglecting setup times can increase makespan by 15%–40% in practical flow shops.

Effects on Production Costs

Longer setup times mean machines are non-productive for extended periods. This reduces the effective capacity of the shop, forcing companies to invest in additional machines or overtime to meet demand. Labor costs also rise because operators may be idle during setups or require premium pay for off-hours changeovers. Indirect costs include increased inventory buffers to cover scheduling uncertainty. By reducing setup times and incorporating them into optimization, manufacturers can lower per-unit costs significantly.

Effects on Lead Time and Customer Satisfaction

Lead time encompasses the entire time from order placement to delivery. Extended setup times increase lead time variability, making it harder to quote accurate delivery dates. Late deliveries damage customer trust and may incur penalties. Efficient scheduling that accounts for setups helps stabilize lead times, enabling companies to offer competitive, reliable delivery promises. In make-to-order environments, this is especially critical.

Mathematical Modeling of Setup Times in Flow Shop Scheduling

To optimize a flow shop with setups, the problem must be formalized mathematically. The classic flow shop model assumes processing times only. With setup times, the model becomes more complex, particularly when setups are sequence-dependent.

Sequence-Dependent Setup Times (SDST)

In an SDST flow shop, the setup time on a machine depends on the job just completed and the next job to be processed. This can be represented by a matrix S where element sij is the setup time when job i precedes job j. The optimization problem becomes a variant of the traveling salesman problem (TSP) for each machine, with the additional constraint of consistent job order across machines. This is NP-hard, and exact methods can only solve small instances.

Mixed-Integer Linear Programming (MILP) Models

MILP formulations for flow shop scheduling with setups use binary variables to represent job sequences and continuous variables for start and end times. Constraints enforce that each job is processed once, that machines process jobs in the same order (permutation flow shop), and that a setup on a machine occurs before a job starts. Objective functions typically minimize makespan or total tardiness. Commercial solvers like CPLEX or Gurobi can handle moderate-sized problems, but for large industrial instances, heuristic approaches are necessary.

Optimization Algorithms Accounting for Setup Times

Given the complexity, researchers and practitioners have developed numerous algorithms—from exact to approximate—to solve flow shop scheduling with setups.

Johnson's Rule Extensions

For the two-machine flow shop without setups, Johnson's rule provides an optimal sequence. Extensions that incorporate small setup times exist, but they are limited. One approach treats setup times as part of processing times or uses modified ranking rules. For larger flow shops, Johnson's rule seldom applies directly.

NEH Heuristic with Setup Considerations

The NEH heuristic is one of the most effective constructive methods for permutation flow shop scheduling. It starts by sorting jobs by total processing time, then inserts jobs one by one into the best position. To account for setups, the insertion cost is calculated using the total time (processing + setup) for each partial sequence. Variants of NEH that consider sequence-dependent setups have been shown to produce high-quality solutions quickly. External resource: NEH heuristic on Wikipedia.

Metaheuristics: Genetic Algorithms and Simulated Annealing

Metaheuristics are widely used for large SDST flow shop problems. A genetic algorithm encodes job sequences as chromosomes and uses crossover and mutation operators to explore the solution space. The fitness function computes the makespan including setup times. Simulated annealing iteratively perturbs the sequence and accepts better solutions, plus some worse ones to avoid local optima. Particle swarm optimization and tabu search are also common. These methods can handle hundreds of jobs and machines and produce near-optimal schedules in reasonable time.

Strategies to Minimize Setup Times

Beyond optimization, reducing the physical setup time is a powerful lever. Shorter setups make scheduling easier and improve shop flexibility.

SMED (Single-Minute Exchange of Die)

Developed by Shigeo Shingo for Toyota, SMED aims to reduce setup times to under ten minutes. It distinguishes between internal setup (performed while the machine is stopped) and external setup (done while the machine is running). The method converts internal steps to external, streamlines remaining steps, and standardizes procedures. Companies have reported setup reductions of 50%–90% using SMED. More information can be found at SMED on Wikipedia.

Job Grouping and Cellular Manufacturing

Grouping jobs by similarity in tooling, material, or process reduces the need for major changeovers. In cellular manufacturing, machines are arranged in cells dedicated to families of parts. Within a cell, setups between family members are minimal. This approach, combined with scheduling that processes entire families together, dramatically cuts total setup time.

Automation and Standardization

Automated tool changers, quick-change fixtures, and programmable machine controllers reduce human involvement and setup duration. Standardized work instructions and operator training ensure consistency. Data acquisition systems can track setup times and highlight areas for improvement.

Case Study: Reducing Setup Times in an Automotive Parts Manufacturer

An automotive supplier of engine components operated a flow shop with five CNC machines. Setup times were sequence-dependent, averaging 25 minutes per changeover. Analysis showed that setups accounted for 35% of total shift time. The company implemented SMED, converting 60% of internal setup steps to external (e.g., pre-staging tools, pre-setting offsets). They also grouped jobs by material grade and tooling requirements. A new NEH-based scheduler incorporated the reduced setup matrix. Over six months, average setup time dropped to 11 minutes, makespan decreased by 22%, and on-time delivery improved from 78% to 96%. The software used was built on the principles described in a study on SDST flow shop optimization by Ribas et al..

Conclusion

Setup times are a decisive factor in flow shop scheduling optimization. They influence makespan, costs, lead times, and customer satisfaction. Manufacturers must first measure and understand their setup patterns—especially sequence dependencies—then apply appropriate mathematical models and optimization algorithms to schedule effectively. Combined with physical reduction techniques like SMED, grouping, and automation, companies can achieve substantial gains in throughput and responsiveness. Integrating setup time data into production planning systems is not optional; it is a foundation for competitive manufacturing in high-mix, low-volume environments.