Anomalies in Special Permutation Flow Shop Scheduling Problems

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. The main contribution of this research is analyzing the intial reason why the anomalies appear in special PFSPs and pointing out the application and the possible research directions of all these three types of anomalies.