Anomalies in Special Permutation Flow Shop Scheduling Problems

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.

Multi-objective Optimization of the Distributed Permutation Flow Shop Scheduling Problem with Transportation and Eligibility Constraints

In this paper,we consider the distributed permutation flow shop scheduling problem(DPFSSP)with transportation and eligibility constrains.Three objectives are taken into account,i.e.,makespan,maximum lateness and total costs(transportation costs and setup costs).To the best of our knowledge,there is no published work on multi-objective optimization of the DPFSSP with transportation and eligibility constraints.First,we present the mathematics model and constructive heuristics for single objective;then,we propose an improved The Nondominated Sorting Genetic Algorithm II(NSGA-II)for the multi-objective DPFSSP to find Pareto optimal solutions,in which a novel solution representation,a new population re-/initialization,effective crossover and mutation operators,as well as local search methods are developed.Based on extensive computational and statistical experiments,the proposed algorithm performs better than the well-known NSGA-II and the Strength Pareto Evolutionary Algorithm 2(SPEA2).

Distributed Flow Shop Scheduling with Sequence-Dependent Setup Times Using an Improved Iterated Greedy Algorithm

To meet the multi-cooperation production demand of enterprises,the distributed permutation flow shop scheduling problem(DPFSP)has become the frontier research in the field of manufacturing systems.In this paper,we investigate the DPFSP by minimizing a makespan criterion under the constraint of sequence-dependent setup times.To solve DPFSPs,significant developments of some metaheuristic algorithms are necessary.In this context,a simple and effective improved iterated greedy(NIG)algorithm is proposed to minimize makespan in DPFSPs.According to the features of DPFSPs,a two-stage local search based on single job swapping and job block swapping within the key factory is designed in the proposed algorithm.We compare the proposed algorithm with state-of-the-art algorithms,including the iterative greedy algorithm(2019),iterative greedy proposed by Ruiz and Pan(2019),discrete differential evolution algorithm(2018),discrete artificial bee colony(2018),and artificial chemical reaction optimization(2017).Simulation results show that NIG outperforms the compared algorithms.

Scheduling deteriorating jobs with rejection on dominant machines

The permutation flow shop scheduling problems with deteriorating jobs and rejection on dominant machines were studied.The objectives are to minimize the makespan of scheduled jobs plus the total rejection penalty and the total completion time of scheduled jobs plus the total rejection penalty.For each objective, polynomial time algorithms based on dynamic programming were presented.