Bottleneck stage and reentrance often exist in real-life manufacturing processes;however,the previous research rarely addresses these two processing conditions in a scheduling problem.In this study,a reentrant hybrid ...Bottleneck stage and reentrance often exist in real-life manufacturing processes;however,the previous research rarely addresses these two processing conditions in a scheduling problem.In this study,a reentrant hybrid flow shop scheduling problem(RHFSP)with a bottleneck stage is considered,and an elite-class teaching-learning-based optimization(ETLBO)algorithm is proposed to minimize maximum completion time.To produce high-quality solutions,teachers are divided into formal ones and substitute ones,and multiple classes are formed.The teacher phase is composed of teacher competition and teacher teaching.The learner phase is replaced with a reinforcement search of the elite class.Adaptive adjustment on teachers and classes is established based on class quality,which is determined by the number of elite solutions in class.Numerous experimental results demonstrate the effectiveness of new strategies,and ETLBO has a significant advantage in solving the considered RHFSP.展开更多
Two-stage hybrid flow shop scheduling has been extensively considered in single-factory settings.However,the distributed two-stage hybrid flow shop scheduling problem(DTHFSP)with fuzzy processing time is seldom invest...Two-stage hybrid flow shop scheduling has been extensively considered in single-factory settings.However,the distributed two-stage hybrid flow shop scheduling problem(DTHFSP)with fuzzy processing time is seldom investigated in multiple factories.Furthermore,the integration of reinforcement learning and metaheuristic is seldom applied to solve DTHFSP.In the current study,DTHFSP with fuzzy processing time was investigated,and a novel Q-learning-based teaching-learning based optimization(QTLBO)was constructed to minimize makespan.Several teachers were recruited for this study.The teacher phase,learner phase,teacher’s self-learning phase,and learner’s self-learning phase were designed.The Q-learning algorithm was implemented by 9 states,4 actions defined as combinations of the above phases,a reward,and an adaptive action selection,which were applied to dynamically adjust the algorithm structure.A number of experiments were conducted.The computational results demonstrate that the new strategies of QTLBO are effective;furthermore,it presents promising results on the considered DTHFSP.展开更多
The hybrid flow shop scheduling problem with unrelated parallel machine is a typical NP-hard combinatorial optimization problem, and it exists widely in chemical, manufacturing and pharmaceutical industry. In this wor...The hybrid flow shop scheduling problem with unrelated parallel machine is a typical NP-hard combinatorial optimization problem, and it exists widely in chemical, manufacturing and pharmaceutical industry. In this work, a novel mathematic model for the hybrid flow shop scheduling problem with unrelated parallel machine(HFSPUPM) was proposed. Additionally, an effective hybrid estimation of distribution algorithm was proposed to solve the HFSPUPM, taking advantage of the features in the mathematic model. In the optimization algorithm, a new individual representation method was adopted. The(EDA) structure was used for global search while the teaching learning based optimization(TLBO) strategy was used for local search. Based on the structure of the HFSPUPM, this work presents a series of discrete operations. Simulation results show the effectiveness of the proposed hybrid algorithm compared with other algorithms.展开更多
Aiming at the hybrid flow-shop (HFS) scheduling that is a complex NP-hard combinatorial problem with wide engineering background, an effective algorithm based on differential evolution (DE) is proposed. By using a...Aiming at the hybrid flow-shop (HFS) scheduling that is a complex NP-hard combinatorial problem with wide engineering background, an effective algorithm based on differential evolution (DE) is proposed. By using a special encoding scheme and combining DE based evolutionary search and local search, the exploration and exploitation abilities are enhanced and well balanced for solving the HFS problems. Simulation results based on some typical problems and comparisons with some existing genetic algorithms demonstrate the proposed algorithm is effective, efficient and robust for solving the HFS problems.展开更多
The connection between production scheduling and transportation scheduling is getting closer in smart manufacturing system, and both of those problems are summarized as NP-hard problems. However, only a few studies ha...The connection between production scheduling and transportation scheduling is getting closer in smart manufacturing system, and both of those problems are summarized as NP-hard problems. However, only a few studies have considered them simultaneously. This paper solves the integrated production and transportation scheduling problem(IPTSP) in hybrid flow shops, which is an extension of the hybrid flow shop scheduling problem(HFSP). In addition to the production scheduling on machines, the transportation scheduling process on automated guided vehicles(AGVs)is considered as another optimization process. In this problem, the transfer tasks of jobs are performed by a certain number of AGVs. To solve it, we make some preparation(including the establishment of task pool, the new solution representation and the new solution evaluation), which can ensure that satisfactory solutions can be found efficiently while appropriately reducing the scale of search space. Then, an effective genetic tabu search algorithm is used to minimize the makespan. Finally, two groups of instances are designed and three types of experiments are conducted to evaluate the performance of the proposed method. The results show that the proposed method is effective to solve the integrated production and transportation scheduling problem.展开更多
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.展开更多
An integrated model is presented to schedule the container handling system. The objective is to improve the coop- eration between different types of equipments, and to increase the productivity of the terminal. The pr...An integrated model is presented to schedule the container handling system. The objective is to improve the coop- eration between different types of equipments, and to increase the productivity of the terminal. The problem is formulated as a Hybrid Flow Shop Scheduling problem with precedence constraint, setup times and blocking (HFSS-B). A tabu search algorithm is proposed to solve this problem. The quality and efficiency of the proposed algorithm is analyzed from the computational point of view.展开更多
针对可重入制造系统多具有多品种、大规模、混流生产等特点,构建带批处理机的可重入混合流水车间调度问题(reentrant hybrid flow shop scheduling problem with batch processors,BPRHFSP)模型,提出一种改进的多目标蜉蝣算法(multi-obj...针对可重入制造系统多具有多品种、大规模、混流生产等特点,构建带批处理机的可重入混合流水车间调度问题(reentrant hybrid flow shop scheduling problem with batch processors,BPRHFSP)模型,提出一种改进的多目标蜉蝣算法(multi-objective mayfly algorithm,MOMA)进行求解。提出了单件加工阶段和批处理阶段的解码规则;设计了基于Logistic混沌映射的反向学习初始化策略、改进的蜉蝣交配和变异策略,提高了算法初始解的质量和局部搜索能力;根据编码规则设计了基于变邻域下降搜索的蜉蝣运动策略,优化了种群方向。通过对不同规模大量测试算例的仿真实验,验证了MOMA相比传统算法求解BP-RHFSP更具有效性和优越性。所提出的模型能够反映生产的基础特征,达到减少最大完工时间、机器负载和碳排放的目的。展开更多
This paper addresses the Energy-Aware Distributed Hybrid Flow Shop Scheduling Problem with Multiprocessor Tasks(EADHFSPMT)by considering two objectives simultaneously,i.e.,makespan and total energy consumption.It cons...This paper addresses the Energy-Aware Distributed Hybrid Flow Shop Scheduling Problem with Multiprocessor Tasks(EADHFSPMT)by considering two objectives simultaneously,i.e.,makespan and total energy consumption.It consists of three sub-problems,i.e.,job assignment between factories,job sequence in each factory,and machine allocation for each job.We present a mixed inter linear programming model and propose a Novel MultiObjective Evolutionary Algorithm based on Decomposition(NMOEA/D).We specially design a decoding scheme according to the characteristics of the EADHFSPMT.To initialize a population with certain diversity,four different rules are utilized.Moreover,a cooperative search is designed to produce new solutions based on different types of relationship between any solution and its neighbors.To enhance the quality of solutions,two local intensification operators are implemented according to the problem characteristics.In addition,a dynamic adjustment strategy for weight vectors is designed to balance the diversity and convergence,which can adaptively modify weight vectors according to the distribution of the non-dominated front.Extensive computational experiments are carried out by using a number of benchmark instances,which demonstrate the effectiveness of the above special designs.The statistical comparisons to the existing algorithms also verify the superior performances of the NMOEA/D.展开更多
This paper studies learning effect as a resource utilization technique that can model improvement in worker's ability as a result of repeating similar tasks. By considering learning of workers while performing setup ...This paper studies learning effect as a resource utilization technique that can model improvement in worker's ability as a result of repeating similar tasks. By considering learning of workers while performing setup times, a schedule can be determined to place jobs that share similar tools and fixtures next to each other. The purpose of this paper is to schedule a set of jobs in a hybrid flow shop (HFS) environment with learning effect while minimizing two objectives that are in conflict: namely maximum completion time (makespan) and total tardiness. Minimizing makespan is desirable from an internal efficiency viewpoint, but may result in individual jobs being scheduled past their due date, causing customer dissatisfaction and penalty costs. A bi-objective mixed integer programming model is developed, and the complexity of the developed bi-objective model is compared against the bi-criteria one through numerical examples. The effect of worker learning on the structure of assigned jobs to machines and their sequences is analyzed. Two solution methods based on the hybrid water flow like algorithm and non-dominated sorting and ranking concepts are proposed to solve the problem. The quality of the approximated sets of Pareto solutions is evaluated using several performance criteria. The results show that the proposed algorithms with learning effect perform well in reducing setup times and eliminate the need for setups itself through proper scheduling.展开更多
基金the National Natural Science Foundation of China(Grant Number 61573264).
文摘Bottleneck stage and reentrance often exist in real-life manufacturing processes;however,the previous research rarely addresses these two processing conditions in a scheduling problem.In this study,a reentrant hybrid flow shop scheduling problem(RHFSP)with a bottleneck stage is considered,and an elite-class teaching-learning-based optimization(ETLBO)algorithm is proposed to minimize maximum completion time.To produce high-quality solutions,teachers are divided into formal ones and substitute ones,and multiple classes are formed.The teacher phase is composed of teacher competition and teacher teaching.The learner phase is replaced with a reinforcement search of the elite class.Adaptive adjustment on teachers and classes is established based on class quality,which is determined by the number of elite solutions in class.Numerous experimental results demonstrate the effectiveness of new strategies,and ETLBO has a significant advantage in solving the considered RHFSP.
文摘Two-stage hybrid flow shop scheduling has been extensively considered in single-factory settings.However,the distributed two-stage hybrid flow shop scheduling problem(DTHFSP)with fuzzy processing time is seldom investigated in multiple factories.Furthermore,the integration of reinforcement learning and metaheuristic is seldom applied to solve DTHFSP.In the current study,DTHFSP with fuzzy processing time was investigated,and a novel Q-learning-based teaching-learning based optimization(QTLBO)was constructed to minimize makespan.Several teachers were recruited for this study.The teacher phase,learner phase,teacher’s self-learning phase,and learner’s self-learning phase were designed.The Q-learning algorithm was implemented by 9 states,4 actions defined as combinations of the above phases,a reward,and an adaptive action selection,which were applied to dynamically adjust the algorithm structure.A number of experiments were conducted.The computational results demonstrate that the new strategies of QTLBO are effective;furthermore,it presents promising results on the considered DTHFSP.
基金Projects(61573144,61773165,61673175,61174040)supported by the National Natural Science Foundation of ChinaProject(222201717006)supported by the Fundamental Research Funds for the Central Universities,China
文摘The hybrid flow shop scheduling problem with unrelated parallel machine is a typical NP-hard combinatorial optimization problem, and it exists widely in chemical, manufacturing and pharmaceutical industry. In this work, a novel mathematic model for the hybrid flow shop scheduling problem with unrelated parallel machine(HFSPUPM) was proposed. Additionally, an effective hybrid estimation of distribution algorithm was proposed to solve the HFSPUPM, taking advantage of the features in the mathematic model. In the optimization algorithm, a new individual representation method was adopted. The(EDA) structure was used for global search while the teaching learning based optimization(TLBO) strategy was used for local search. Based on the structure of the HFSPUPM, this work presents a series of discrete operations. Simulation results show the effectiveness of the proposed hybrid algorithm compared with other algorithms.
基金supported by the National Natural Science Fundation of China (60774082 70871065+2 种基金 60834004)the Program for New Century Excellent Talents in University (NCET-10-0505)the Doctoral Program Foundation of Institutions of Higher Education of China(20100002110014)
文摘Aiming at the hybrid flow-shop (HFS) scheduling that is a complex NP-hard combinatorial problem with wide engineering background, an effective algorithm based on differential evolution (DE) is proposed. By using a special encoding scheme and combining DE based evolutionary search and local search, the exploration and exploitation abilities are enhanced and well balanced for solving the HFS problems. Simulation results based on some typical problems and comparisons with some existing genetic algorithms demonstrate the proposed algorithm is effective, efficient and robust for solving the HFS problems.
基金Supported by National Key R&D Program of China (Grant No. 2019YFB1704603)National Natural Science Foundation of China (Grant Nos. U21B2029 and 51825502)。
文摘The connection between production scheduling and transportation scheduling is getting closer in smart manufacturing system, and both of those problems are summarized as NP-hard problems. However, only a few studies have considered them simultaneously. This paper solves the integrated production and transportation scheduling problem(IPTSP) in hybrid flow shops, which is an extension of the hybrid flow shop scheduling problem(HFSP). In addition to the production scheduling on machines, the transportation scheduling process on automated guided vehicles(AGVs)is considered as another optimization process. In this problem, the transfer tasks of jobs are performed by a certain number of AGVs. To solve it, we make some preparation(including the establishment of task pool, the new solution representation and the new solution evaluation), which can ensure that satisfactory solutions can be found efficiently while appropriately reducing the scale of search space. Then, an effective genetic tabu search algorithm is used to minimize the makespan. Finally, two groups of instances are designed and three types of experiments are conducted to evaluate the performance of the proposed method. The results show that the proposed method is effective to solve the integrated production and transportation scheduling problem.
基金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.
文摘An integrated model is presented to schedule the container handling system. The objective is to improve the coop- eration between different types of equipments, and to increase the productivity of the terminal. The problem is formulated as a Hybrid Flow Shop Scheduling problem with precedence constraint, setup times and blocking (HFSS-B). A tabu search algorithm is proposed to solve this problem. The quality and efficiency of the proposed algorithm is analyzed from the computational point of view.
基金supported by the National Natural Science Fund for Distinguished Young Scholars of China(No.61525304)the National Natural Science Foundation of China(No.61873328)。
文摘This paper addresses the Energy-Aware Distributed Hybrid Flow Shop Scheduling Problem with Multiprocessor Tasks(EADHFSPMT)by considering two objectives simultaneously,i.e.,makespan and total energy consumption.It consists of three sub-problems,i.e.,job assignment between factories,job sequence in each factory,and machine allocation for each job.We present a mixed inter linear programming model and propose a Novel MultiObjective Evolutionary Algorithm based on Decomposition(NMOEA/D).We specially design a decoding scheme according to the characteristics of the EADHFSPMT.To initialize a population with certain diversity,four different rules are utilized.Moreover,a cooperative search is designed to produce new solutions based on different types of relationship between any solution and its neighbors.To enhance the quality of solutions,two local intensification operators are implemented according to the problem characteristics.In addition,a dynamic adjustment strategy for weight vectors is designed to balance the diversity and convergence,which can adaptively modify weight vectors according to the distribution of the non-dominated front.Extensive computational experiments are carried out by using a number of benchmark instances,which demonstrate the effectiveness of the above special designs.The statistical comparisons to the existing algorithms also verify the superior performances of the NMOEA/D.
文摘This paper studies learning effect as a resource utilization technique that can model improvement in worker's ability as a result of repeating similar tasks. By considering learning of workers while performing setup times, a schedule can be determined to place jobs that share similar tools and fixtures next to each other. The purpose of this paper is to schedule a set of jobs in a hybrid flow shop (HFS) environment with learning effect while minimizing two objectives that are in conflict: namely maximum completion time (makespan) and total tardiness. Minimizing makespan is desirable from an internal efficiency viewpoint, but may result in individual jobs being scheduled past their due date, causing customer dissatisfaction and penalty costs. A bi-objective mixed integer programming model is developed, and the complexity of the developed bi-objective model is compared against the bi-criteria one through numerical examples. The effect of worker learning on the structure of assigned jobs to machines and their sequences is analyzed. Two solution methods based on the hybrid water flow like algorithm and non-dominated sorting and ranking concepts are proposed to solve the problem. The quality of the approximated sets of Pareto solutions is evaluated using several performance criteria. The results show that the proposed algorithms with learning effect perform well in reducing setup times and eliminate the need for setups itself through proper scheduling.