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 diffe...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.展开更多
A new concept of multi-shop （M ） is put forward which contains all basic shops including open shop （O）, job shop （J ）, flow shop （F ） and hybrid flow shop （H ） so that these basic shop can be scheduled toget...A new concept of multi-shop （M ） is put forward which contains all basic shops including open shop （O）, job shop （J ）, flow shop （F ） and hybrid flow shop （H ） so that these basic shop can be scheduled together. Several algorithms including ant colony optimization （ACO）, most work remaining （MWR）, least work remaining （LWR）, longest processing time （LPT） and shortest processing time （SPT） are used for scheduling the M. Numerical experiments of the M adopting data of some car and reC series benchmark instances are tested. The results show that the ACO algorithm has better performance for scheduling the M than the other algorithms, if minimizing the makespan （ Cmax^＊） is taken as the objective function. As a comparison, the separate shops contained in the M are also scheduled by the ACO algorithm for the same objective function, when the completing time of the jobs in the previous shop is taken as the ready time of these jobs in the following shop. The results show that the M has the advantage of shortening the makespan upon separate shops.展开更多
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...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).展开更多
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 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.展开更多
基金Supported by National Natural Science Foundation of China(Grant No.51825502).
文摘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.
基金This project is supported by National Natural Science Foundation of China (No. 50575137)Provincial Natural Science Foundation of Zhejiang, China (No. Z604342)Scientific Research Fund of Zhejiang Provincial Educational Committee, China (No. 20051643).
文摘A new concept of multi-shop （M ） is put forward which contains all basic shops including open shop （O）, job shop （J ）, flow shop （F ） and hybrid flow shop （H ） so that these basic shop can be scheduled together. Several algorithms including ant colony optimization （ACO）, most work remaining （MWR）, least work remaining （LWR）, longest processing time （LPT） and shortest processing time （SPT） are used for scheduling the M. Numerical experiments of the M adopting data of some car and reC series benchmark instances are tested. The results show that the ACO algorithm has better performance for scheduling the M than the other algorithms, if minimizing the makespan （ Cmax^＊） is taken as the objective function. As a comparison, the separate shops contained in the M are also scheduled by the ACO algorithm for the same objective function, when the completing time of the jobs in the previous shop is taken as the ready time of these jobs in the following shop. The results show that the M has the advantage of shortening the makespan upon separate shops.
基金国家科技公关计划项目(the Key Technologies R&D Program of China under Grant No.2001BA201A32)国家高技术研究发展计划(863) (the National High-Tech Research and Development Plan of China under Grant No.2002AA415270)
基金This work was supported by National Natural Science Foundation of China(NNSFC) 10471096and Shenyang Normal University Doctoral Foundation 55440101007.
基金This research was partially supported by the National Natural Science Foundation of China(Nos.71390334 and 11271356).
文摘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).
文摘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.
