Abstract
Recent researches show that there are some anomalies, which are not satisfied with common sense, appearing in some special permutation flow shop scheduling problems (PFSPs). These anomalies can be divided into three different types, such as changing the processing time of some operations, changing the number of total jobs and changing the number of total machines. This paper summarizes these three types of anomalies showing in the special PFSPs and gives some examples to make them better understood. The extended critical path is proposed and the reason why these anomalies happen in special PFSPs is given: anomalies will occur in these special PFSPs when the time of the operations on the reverse critical path changes. After that, the further reason for these anomalies is presented that when any one of these three types of anomalies happens, the original constraint in the special PFSPs is destroyed, which makes the anomalies appear. Finally, the application of these anomalies in production practice is given through examples and also with the possible research directions.
Introduction
In industrial engineering, the Permutation Flow Shop Scheduling Problem (PFSP) is a foundational model where a set of jobs must be processed through a sequence of machines in the same order. Under standard conditions, intuition dictates that increasing the workload—whether by lengthening a task, adding a job, or introducing more machines—will inevitably increase the total completion time, or makespan. However, in specialized manufacturing environments with rigid constraints, this "common sense" logic fails. This paper explores these counter-intuitive "anomalies" where adding work actually accelerates the overall process.
The Paradox of Special Constraints
The anomalies primarily appear in three types of constrained PFSPs:
- No-Wait (NWFSP): Jobs must move to the next machine immediately upon completion of the previous stage, with zero buffer time.
- No-Idle (NIFSP): Once a machine starts its first job, it must continue processing without any idle periods until all assigned jobs are finished.
- Synchronous (SFSP): All jobs move to their next respective stages simultaneously.
In these environments, constraints create a rigid interdependency between tasks. The authors demonstrate that these rigidities can sometimes be "broken" to achieve a more efficient global state by strategically introducing what appears to be a local inefficiency.
The Extended Critical Path Method
To explain these phenomena, the authors introduce the Extended Critical Path. While a traditional critical path identifies the longest sequence of dependent tasks, the extended version accounts for the specific constraints of the shop. It defines:
- Forward Critical Path Segments: Periods of active processing.
- Reverse Critical Path Segments: Gaps or forced delays dictated by the shop's rules (e.g., the time a job must wait to ensure a machine remains "no-idle").
Mathematically, the total makespan is the sum of forward segments minus the sum of reverse segments. Consequently, increasing the duration of an operation located on a reverse critical path segment actually reduces the final makespan.
Experimental Results: The Processing Time Anomaly
The most striking anomaly occurs when increasing the processing time of a single operation reduces the total makespan. Consider a No-Idle Flow Shop Problem (NIFSP) with three jobs and three machines.
In the initial state shown in Figure 1, the makespan is 25 units. By increasing the processing time of operation $O_{22}$ (the second operation of the second job) from 3 to 5 units, the schedule is forced to re-align.
As seen in Figure 2, this local "slowdown" actually resolves a bottleneck created by the no-idle constraint, leading to a global reduction in completion time from 25 to 23 units.
Other Anomalies and Practical Implications
Beyond processing times, the authors identify two other anomaly types:
- Type 2 (Number of Jobs): Inserting a small "dummy" job between existing jobs can break a restrictive sequence, reducing the total time for the original set of jobs.
- Type 3 (Number of Machines): Adding an extra machine stage in a No-Wait environment can provide the necessary "slack" to optimize the flow of jobs, paradoxically finishing the sequence faster than with fewer machines.
These findings have significant implications for production management. If a factory is bound by strict "no-idle" or "no-wait" rules, it may be economically beneficial to intentionally introduce "anomalies" to meet tight delivery deadlines.
Conclusion
The core reason for these anomalies is the "destruction" of original constraints. By identifying operations on the reverse critical path, managers can strategically adjust workloads to bypass the inefficiencies inherent in rigid scheduling models. Future research will focus on scaling these insights to large-scale industrial systems and developing automated optimization algorithms that leverage these paradoxes.
Summary updated