To solve the sparse reward problem of job-shop scheduling by deep reinforcement learning,a deep reinforcement learning framework considering sparse reward problem is proposed.The job shop scheduling problem is transfo...To solve the sparse reward problem of job-shop scheduling by deep reinforcement learning,a deep reinforcement learning framework considering sparse reward problem is proposed.The job shop scheduling problem is transformed into Markov decision process,and six state features are designed to improve the state feature representation by using two-way scheduling method,including four state features that distinguish the optimal action and two state features that are related to the learning goal.An extended variant of graph isomorphic network GIN++is used to encode disjunction graphs to improve the performance and generalization ability of the model.Through iterative greedy algorithm,random strategy is generated as the initial strategy,and the action with the maximum information gain is selected to expand it to optimize the exploration ability of Actor-Critic algorithm.Through validation of the trained policy model on multiple public test data sets and comparison with other advanced DRL methods and scheduling rules,the proposed method reduces the minimum average gap by 3.49%,5.31%and 4.16%,respectively,compared with the priority rule-based method,and 5.34%compared with the learning-based method.11.97%and 5.02%,effectively improving the accuracy of DRL to solve the approximate solution of JSSP minimum completion time.展开更多
An improved adaptive particle swarm optimization(IAPSO)algorithm is presented for solving the minimum makespan problem of job shop scheduling problem(JSP).Inspired by hormone modulation mechanism,an adaptive hormonal ...An improved adaptive particle swarm optimization(IAPSO)algorithm is presented for solving the minimum makespan problem of job shop scheduling problem(JSP).Inspired by hormone modulation mechanism,an adaptive hormonal factor(HF),composed of an adaptive local hormonal factor(H l)and an adaptive global hormonal factor(H g),is devised to strengthen the information connection between particles.Using HF,each particle of the swarm can adjust its position self-adaptively to avoid premature phenomena and reach better solution.The computational results validate the effectiveness and stability of the proposed IAPSO,which can not only find optimal or close-to-optimal solutions but also obtain both better and more stability results than the existing particle swarm optimization(PSO)algorithms.展开更多
A modified bottleneck-based （MB） heuristic for large-scale job-shop scheduling problems with a welldefined bottleneck is suggested, which is simpler but more tailored than the shifting bottleneck （SB） procedure. I...A modified bottleneck-based （MB） heuristic for large-scale job-shop scheduling problems with a welldefined bottleneck is suggested, which is simpler but more tailored than the shifting bottleneck （SB） procedure. In this algorithm, the bottleneck is first scheduled optimally while the non-bottleneck machines are subordinated around the solutions of the bottleneck schedule by some effective dispatching rules. Computational results indicate that the MB heuristic can achieve a better tradeoff between solution quality and computational time compared to SB procedure for medium-size problems. Furthermore, it can obtain a good solution in a short time for large-scale jobshop scheduling problems.展开更多
The traditional production planning and scheduling problems consider performance indicators like time, cost and quality as optimization objectives in manufacturing processes. However, environmentally-friendly factors ...The traditional production planning and scheduling problems consider performance indicators like time, cost and quality as optimization objectives in manufacturing processes. However, environmentally-friendly factors like energy consumption of production have not been completely taken into consideration. Against this background, this paper addresses an approach to modify a given schedule generated by a production plarming and scheduling system in a job shop floor, where machine tools can work at different cutting speeds. It can adjust the cutting speeds of the operations while keeping the original assignment and processing sequence of operations of each job fixed in order to obtain energy savings. First, the proposed approach, based on a mixed integer programming mathematical model, changes the total idle time of the given schedule to minimize energy consumption in the job shop floor while accepting the optimal solution of the scheduling objective, makespan. Then, a genetic-simulated annealing algorithm is used to explore the optimal solution due to the fact that the problem is strongly NP-hard. Finally, the effectiveness of the approach is performed small- and large-size instances, respectively. The experimental results show that the approach can save 5%-10% of the average energy consumption while accepting the optimal solution of the makespan in small-size instances. In addition, the average maximum energy saving ratio can reach to 13%. And it can save approximately 1%-4% of the average energy consumption and approximately 2.4% of the average maximum energy while accepting the near-optimal solution of the makespan in large-size instances. The proposed research provides an interesting point to explore an energy-aware schedule optimization for a traditional production planning and scheduling problem.展开更多
The issue of reducing energy consumption for the job-shop scheduling problem in machining systems is addressed, whose dual objectives are to minimize both the energy consumption and the makespan. First, the bi- object...The issue of reducing energy consumption for the job-shop scheduling problem in machining systems is addressed, whose dual objectives are to minimize both the energy consumption and the makespan. First, the bi- objective model for the job-shop scheduling problem is proposed. The objective function value of the model represents synthesized optimization of energy consumption and makespan. Then, a heuristic algorithm is developed to locate the optimal or near optimal solutions of the model based on the Tabu search mechanism. Finally, the experimental case is presented to demonstrate the effectiveness of the proposed model and the algorithm.展开更多
The meta-heuristic algorithm with local search is an excellent choice for the job-shop scheduling problem(JSP).However,due to the unique nature of the JSP,local search may generate infeasible neighbourhood solutions.I...The meta-heuristic algorithm with local search is an excellent choice for the job-shop scheduling problem(JSP).However,due to the unique nature of the JSP,local search may generate infeasible neighbourhood solutions.In the existing literature,although some domain knowledge of the JSP can be used to avoid infeasible solutions,the constraint conditions in this domain knowledge are sufficient but not necessary.It may lose many feasible solutions and make the local search inadequate.By analysing the causes of infeasible neighbourhood solutions,this paper further explores the domain knowledge contained in the JSP and proposes the sufficient and necessary constraint conditions to find all feasible neighbourhood solutions,allowing the local search to be carried out thoroughly.With the proposed conditions,a new neighbourhood structure is designed in this paper.Then,a fast calculation method for all feasible neighbourhood solutions is provided,significantly reducing the calculation time compared with ordinary methods.A set of standard benchmark instances is used to evaluate the performance of the proposed neighbourhood structure and calculation method.The experimental results show that the calculation method is effective,and the new neighbourhood structure has more reliability and superiority than the other famous and influential neighbourhood structures,where 90%of the results are the best compared with three other well-known neighbourhood structures.Finally,the result from a tabu search algorithm with the new neighbourhood structure is compared with the current best results,demonstrating the superiority of the proposed neighbourhood structure.展开更多
In this paper, we propose a new genetic algorithm for job-shop scheduling problems （JSP）. The proposed method uses the operation-based representation, based on schema theorem and building block hypothesis, a new cro...In this paper, we propose a new genetic algorithm for job-shop scheduling problems （JSP）. The proposed method uses the operation-based representation, based on schema theorem and building block hypothesis, a new crossover is proposed ： By selecting short, low order highly fit schemas to genetic operator, the crossover can exchange meaningful ordering information of parents effectively and can search the global optimization. Simulation results on MT benchmark problem coded by C ＋ ＋ show that our genetic operators are very powerful and suitable to job-shop scheduling problems and our method outperforms the previous GA-based approaches.展开更多
Meta-heuristic algorithms search the problem solution space to obtain a satisfactory solution within a reasonable timeframe.By combining domain knowledge of the specific optimization problem,the search efficiency and ...Meta-heuristic algorithms search the problem solution space to obtain a satisfactory solution within a reasonable timeframe.By combining domain knowledge of the specific optimization problem,the search efficiency and quality of meta-heuristic algorithms can be significantly improved,making it crucial to identify and summarize domain knowledge within the problem.In this paper,we summarize and analyze domain knowledge that can be applied to meta-heuristic algorithms in the job-shop scheduling problem(JSP).Firstly,this paper delves into the importance of domain knowledge in optimization algorithm design.After that,the development of different methods for the JSP are reviewed,and the domain knowledge in it for meta-heuristic algorithms is summarized and classified.Applications of this domain knowledge are analyzed,showing it is indispensable in ensuring the optimization performance of meta-heuristic algorithms.Finally,this paper analyzes the relationship among domain knowledge,optimization problems,and optimization algorithms,and points out the shortcomings of the existing research and puts forward research prospects.This paper comprehensively summarizes the domain knowledge in the JSP,and discusses the relationship between the optimization problems,optimization algorithms and domain knowledge,which provides a research direction for the metaheuristic algorithm design for solving the JSP in the future.展开更多
The shop scheduling problem with limited buffers has broad applications in real-world production scenarios,so this research direction is of great practical significance.However,there is currently little research on th...The shop scheduling problem with limited buffers has broad applications in real-world production scenarios,so this research direction is of great practical significance.However,there is currently little research on the hybrid flow shop scheduling problem with limited buffers(LBHFSP).This paper deeply investigates the LBHFSP to optimize the goal of the total completion time.To better solve the LBHFSP,a multi-level subpopulation-based particle swarm optimization algorithm(MLPSO)is proposed,which is founded on the attributes of the LBHFSP and the shortcomings of the basic PSO(particle swarm optimization)algorithm.In MLPSO,firstly,considering the impact of the limited buffers on the process of subsequent operations,a specific circular decoding strategy is developed to accommodate the characteristics of limited buffers.Secondly,an initialization strategy based on blocking time is designed to enhance the quality and diversity of the initial population.Afterward,a multi-level subpopulation collaborative search is developed to prevent being trapped in a local optimum and improve the global exploration capability.Additionally,a local search strategy based on the first blocked job is designed to enhance the MLPSO algorithm’s exploitation capability.Lastly,numerous experiments are carried out to test the performance of the proposed MLPSO by comparing it with classical intelligent optimization and popular algorithms in recent years.The results confirm that the proposed MLPSO has an outstanding performance when compared to other algorithms when solving LBHFSP.展开更多
With the development of economic globalization,distributedmanufacturing is becomingmore andmore prevalent.Recently,integrated scheduling of distributed production and assembly has captured much concern.This research s...With the development of economic globalization,distributedmanufacturing is becomingmore andmore prevalent.Recently,integrated scheduling of distributed production and assembly has captured much concern.This research studies a distributed flexible job shop scheduling problem with assembly operations.Firstly,a mixed integer programming model is formulated to minimize the maximum completion time.Secondly,a Q-learning-assisted coevolutionary algorithmis presented to solve themodel:(1)Multiple populations are developed to seek required decisions simultaneously;(2)An encoding and decoding method based on problem features is applied to represent individuals;(3)A hybrid approach of heuristic rules and random methods is employed to acquire a high-quality population;(4)Three evolutionary strategies having crossover and mutation methods are adopted to enhance exploration capabilities;(5)Three neighborhood structures based on problem features are constructed,and a Q-learning-based iterative local search method is devised to improve exploitation abilities.The Q-learning approach is applied to intelligently select better neighborhood structures.Finally,a group of instances is constructed to perform comparison experiments.The effectiveness of the Q-learning approach is verified by comparing the developed algorithm with its variant without the Q-learning method.Three renowned meta-heuristic algorithms are used in comparison with the developed algorithm.The comparison results demonstrate that the designed method exhibits better performance in coping with the formulated problem.展开更多
A new heuristic algorithm is proposed for the problem of finding the minimummakespan in the job-shop scheduling problem. The new algorithm is based on the principles ofparticle swarm optimization (PSO). PSO employs a ...A new heuristic algorithm is proposed for the problem of finding the minimummakespan in the job-shop scheduling problem. The new algorithm is based on the principles ofparticle swarm optimization (PSO). PSO employs a collaborative population-based search, which isinspired by the social behavior of bird flocking. It combines local search (by self experience) andglobal search (by neighboring experience), possessing high search efficiency. Simulated annealing(SA) employs certain probability to avoid becoming trapped in a local optimum and the search processcan be controlled by the cooling schedule. By reasonably combining these two different searchalgorithms, a general, fast and easily implemented hybrid optimization algorithm, named HPSO, isdeveloped. The effectiveness and efficiency of the proposed PSO-based algorithm are demonstrated byapplying it to some benchmark job-shop scheduling problems and comparing results with otheralgorithms in literature. Comparing results indicate that PSO-based algorithm is a viable andeffective approach for the job-shop scheduling problem.展开更多
Safe and efficient sortie scheduling on the confined flight deck is crucial for maintaining high combat effectiveness of the aircraft carrier.The primary difficulty exactly lies in the spatiotemporal coordination,i.e....Safe and efficient sortie scheduling on the confined flight deck is crucial for maintaining high combat effectiveness of the aircraft carrier.The primary difficulty exactly lies in the spatiotemporal coordination,i.e.,allocation of limited supporting resources and collision-avoidance between heterogeneous dispatch entities.In this paper,the problem is investigated in the perspective of hybrid flow-shop scheduling problem by synthesizing the precedence,space and resource constraints.Specifically,eight processing procedures are abstracted,where tractors,preparing spots,catapults,and launching are virtualized as machines.By analyzing the constraints in sortie scheduling,a mixed-integer planning model is constructed.In particular,the constraint on preparing spot occupancy is improved to further enhance the sortie efficiency.The basic trajectory library for each dispatch entity is generated and a delayed strategy is integrated to address the collision-avoidance issue.To efficiently solve the formulated HFSP,which is essentially a combinatorial problem with tightly coupled constraints,a chaos-initialized genetic algorithm is developed.The solution framework is validated by the simulation environment referring to the Fort-class carrier,exhibiting higher sortie efficiency when compared to existing strategies.And animation of the simulation results is available at www.bilibili.com/video/BV14t421A7Tt/.The study presents a promising supporting technique for autonomous flight deck operation in the foreseeable future,and can be easily extended to other supporting scenarios,e.g.,ammunition delivery and aircraft maintenance.展开更多
The standard genetic algorithm has limitations of a low convergence rate and premature convergence in solving the job-shop scheduling problem.To overcome these limitations,this paper presents a new improved hybrid gen...The standard genetic algorithm has limitations of a low convergence rate and premature convergence in solving the job-shop scheduling problem.To overcome these limitations,this paper presents a new improved hybrid genetic algorithm on the basis of the idea of graft in botany.Through the introduction of a grafted population and crossover probability matrix,this algorithm accelerates the convergence rate greatly and also increases the ability to fight premature convergence.Finally,the approach is tested on a set of standard instances taken from the literature and compared with other approaches.The computation results validate the effectiveness of the proposed algorithm.展开更多
Marine container terminal(MCT)plays a key role in the marine intelligent transportation system and international logistics system.However,the efficiency of resource scheduling significantly influences the operation pe...Marine container terminal(MCT)plays a key role in the marine intelligent transportation system and international logistics system.However,the efficiency of resource scheduling significantly influences the operation performance of MCT.To solve the practical resource scheduling problem(RSP)in MCT efficiently,this paper has contributions to both the problem model and the algorithm design.Firstly,in the problem model,different from most of the existing studies that only consider scheduling part of the resources in MCT,we propose a unified mathematical model for formulating an integrated RSP.The new integrated RSP model allocates and schedules multiple MCT resources simultaneously by taking the total cost minimization as the objective.Secondly,in the algorithm design,a pre-selection-based ant colony system(PACS)approach is proposed based on graphic structure solution representation and a pre-selection strategy.On the one hand,as the RSP can be formulated as the shortest path problem on the directed complete graph,the graphic structure is proposed to represent the solution encoding to consider multiple constraints and multiple factors of the RSP,which effectively avoids the generation of infeasible solutions.On the other hand,the pre-selection strategy aims to reduce the computational burden of PACS and to fast obtain a higher-quality solution.To evaluate the performance of the proposed novel PACS in solving the new integrated RSP model,a set of test cases with different sizes is conducted.Experimental results and comparisons show the effectiveness and efficiency of the PACS algorithm,which can significantly outperform other state-of-the-art algorithms.展开更多
Job-shop scheduling problem with discretely controllable processing times (JSP-DCPT) is modeled based on the disjunctive graph, and the formulation of JSP-DCPT is presented. A three-step decomposition approach is prop...Job-shop scheduling problem with discretely controllable processing times (JSP-DCPT) is modeled based on the disjunctive graph, and the formulation of JSP-DCPT is presented. A three-step decomposition approach is proposed so that JSP-DCPT can be handled by solving a job-shop scheduling problem (JSP) and a series of discrete time-cost tradeoff problems. To simplify the decomposition approach, the time-cost phase plane is introduced to describe tradeoffs of the discrete time-cost tradeoff problem, and an extreme mode-based set dominant theory is elaborated so that an upper bound is determined to cut discrete time-cost tradeoff problems generated by using the proposed decomposition approach. An extreme mode-based set dominant decomposition algorithm (EMSDDA) is then proposed. Experimental simulations for instance JSPDCPT_FT10, which is designed based on a JSP benchmark FT10, demonstrate the effectiveness of the proposed theory and the decomposition approach.展开更多
Economic globalization has transformed many manufacturing enterprises from a single-plant production mode to a multi-plant cooperative production mode.The distributed flexible job-shop scheduling problem(DFJSP)has bec...Economic globalization has transformed many manufacturing enterprises from a single-plant production mode to a multi-plant cooperative production mode.The distributed flexible job-shop scheduling problem(DFJSP)has become a research hot topic in the field of scheduling because its production is closer to reality.The research of DFJSP is of great significance to the organization and management of actual production process.To solve the heterogeneous DFJSP with minimal completion time,a hybrid chemical reaction optimization(HCRO)algorithm is proposed in this paper.Firstly,a novel encoding-decoding method for flexible manufacturing unit(FMU)is designed.Secondly,half of initial populations are generated by scheduling rule.Combined with the new solution acceptance method of simulated annealing(SA)algorithm,an improved method of critical-FMU is designed to improve the global and local search ability of the algorithm.Finally,the elitist selection strategy and the orthogonal experimental method are introduced to the algorithm to improve the convergence speed and optimize the algorithm parameters.In the experimental part,the effectiveness of the simulated annealing algorithm and the critical-FMU refinement methods is firstly verified.Secondly,in the comparison with other existing algorithms,the proposed optimal scheduling algorithm is not only effective in homogeneous FMUs examples,but also superior to existing algorithms in heterogeneous FMUs arithmetic cases.展开更多
The flexible job-shop scheduling problem(FJSP)with combined processing constraints is a common scheduling problem in mixed-flow production lines.However,traditional methods for classic FJSP cannot be directly applied....The flexible job-shop scheduling problem(FJSP)with combined processing constraints is a common scheduling problem in mixed-flow production lines.However,traditional methods for classic FJSP cannot be directly applied.Targeting this problem,the process state model of a mixed-flow production line is analyzed.On this basis,a mathematical model of a mixed-flow job-shop scheduling problem with combined processing constraints is established based on the traditional FJSP.Then,an improved genetic algorithm with multi-segment encoding,crossover,and mutation is proposed for the mixed-flow production line problem.Finally,the proposed algorithm is applied to the production workshop of missile structural components at an aerospace institute to verify its feasibility and effectiveness.展开更多
The fuzzy goal flexible job-shop scheduling problem （FGFJSP） is the extension of FJSP. Compared with the convention JSP, it can solve the fuzzy goal problem and meet suit requirements of the key job. The multi-objec...The fuzzy goal flexible job-shop scheduling problem （FGFJSP） is the extension of FJSP. Compared with the convention JSP, it can solve the fuzzy goal problem and meet suit requirements of the key job. The multi-object problem, such as the fuzzy cost, the fuzzy due-date, and the fuzzy makespan, etc, can be solved by FGFJSP. To optimize FGFJSP, an individual optimization and colony diversity genetic algorithm （IOCDGA） is presented to accelerate the convergence speed and to avoid the earliness. In IOCDGA, the colony average distance and the colony entropy are defined after the definition of the encoding model. The colony diversity is expressed by the colony average distance and the colony entropy. The crossover probability and the mutation probability are controlled by the colony diversity. The evolution emphasizes that sigle individual or a few individuals evolve into the best in IOCDGA, but not the all in classical GA. Computational results show that the algorithm is applicable and the number of iterations is less.展开更多
In the flexible job-shop scheduling problem （FJSP）, each operation has to be assigned to a machine from a set of capable machines before alocating the assigned operations on all machines. To solve the multi-objectiv...In the flexible job-shop scheduling problem （FJSP）, each operation has to be assigned to a machine from a set of capable machines before alocating the assigned operations on all machines. To solve the multi-objective FJSP, the Grantt graph oriented string representation （GOSR） and the basic manipulation of the genetic algorithm operator are presented. An integrated operator genetic algorithm （IOGA） and its process are described. Comparison between computational results and the latest research shows that the proposed algorithm is effective in reducing the total workload of all machines, the makespan and the critical machine workload.展开更多
基金Shaanxi Provincial Key Research and Development Project(2023YBGY095)and Shaanxi Provincial Qin Chuangyuan"Scientist+Engineer"project(2023KXJ247)Fund support.
文摘To solve the sparse reward problem of job-shop scheduling by deep reinforcement learning,a deep reinforcement learning framework considering sparse reward problem is proposed.The job shop scheduling problem is transformed into Markov decision process,and six state features are designed to improve the state feature representation by using two-way scheduling method,including four state features that distinguish the optimal action and two state features that are related to the learning goal.An extended variant of graph isomorphic network GIN++is used to encode disjunction graphs to improve the performance and generalization ability of the model.Through iterative greedy algorithm,random strategy is generated as the initial strategy,and the action with the maximum information gain is selected to expand it to optimize the exploration ability of Actor-Critic algorithm.Through validation of the trained policy model on multiple public test data sets and comparison with other advanced DRL methods and scheduling rules,the proposed method reduces the minimum average gap by 3.49%,5.31%and 4.16%,respectively,compared with the priority rule-based method,and 5.34%compared with the learning-based method.11.97%and 5.02%,effectively improving the accuracy of DRL to solve the approximate solution of JSSP minimum completion time.
基金Supported by the National Natural Science Foundation of China(51175262)the Research Fund for Doctoral Program of Higher Education of China(20093218110020)+2 种基金the Jiangsu Province Science Foundation for Excellent Youths(BK201210111)the Jiangsu Province Industry-Academy-Research Grant(BY201220116)the Innovative and Excellent Foundation for Doctoral Dissertation of Nanjing University of Aeronautics and Astronautics(BCXJ10-09)
文摘An improved adaptive particle swarm optimization(IAPSO)algorithm is presented for solving the minimum makespan problem of job shop scheduling problem(JSP).Inspired by hormone modulation mechanism,an adaptive hormonal factor(HF),composed of an adaptive local hormonal factor(H l)and an adaptive global hormonal factor(H g),is devised to strengthen the information connection between particles.Using HF,each particle of the swarm can adjust its position self-adaptively to avoid premature phenomena and reach better solution.The computational results validate the effectiveness and stability of the proposed IAPSO,which can not only find optimal or close-to-optimal solutions but also obtain both better and more stability results than the existing particle swarm optimization(PSO)algorithms.
基金the National Natural Science Foundation of China (6027401360474002)Shanghai Development Found for Science and Technology (04DZ11008).
文摘A modified bottleneck-based （MB） heuristic for large-scale job-shop scheduling problems with a welldefined bottleneck is suggested, which is simpler but more tailored than the shifting bottleneck （SB） procedure. In this algorithm, the bottleneck is first scheduled optimally while the non-bottleneck machines are subordinated around the solutions of the bottleneck schedule by some effective dispatching rules. Computational results indicate that the MB heuristic can achieve a better tradeoff between solution quality and computational time compared to SB procedure for medium-size problems. Furthermore, it can obtain a good solution in a short time for large-scale jobshop scheduling problems.
基金Supported by a Marie Curie International Research Staff Exchange Scheme Fellowship within the 7th European Community Framework Program(Grant No.294931)National Science Foundation of China(Grant No.51175262)+1 种基金Jiangsu Provincial Science Foundation for Excellent Youths of China(Grant No.BK2012032)Jiangsu Provincial Industry-Academy-Research Grant of China(Grant No.BY201220116)
文摘The traditional production planning and scheduling problems consider performance indicators like time, cost and quality as optimization objectives in manufacturing processes. However, environmentally-friendly factors like energy consumption of production have not been completely taken into consideration. Against this background, this paper addresses an approach to modify a given schedule generated by a production plarming and scheduling system in a job shop floor, where machine tools can work at different cutting speeds. It can adjust the cutting speeds of the operations while keeping the original assignment and processing sequence of operations of each job fixed in order to obtain energy savings. First, the proposed approach, based on a mixed integer programming mathematical model, changes the total idle time of the given schedule to minimize energy consumption in the job shop floor while accepting the optimal solution of the scheduling objective, makespan. Then, a genetic-simulated annealing algorithm is used to explore the optimal solution due to the fact that the problem is strongly NP-hard. Finally, the effectiveness of the approach is performed small- and large-size instances, respectively. The experimental results show that the approach can save 5%-10% of the average energy consumption while accepting the optimal solution of the makespan in small-size instances. In addition, the average maximum energy saving ratio can reach to 13%. And it can save approximately 1%-4% of the average energy consumption and approximately 2.4% of the average maximum energy while accepting the near-optimal solution of the makespan in large-size instances. The proposed research provides an interesting point to explore an energy-aware schedule optimization for a traditional production planning and scheduling problem.
文摘The issue of reducing energy consumption for the job-shop scheduling problem in machining systems is addressed, whose dual objectives are to minimize both the energy consumption and the makespan. First, the bi- objective model for the job-shop scheduling problem is proposed. The objective function value of the model represents synthesized optimization of energy consumption and makespan. Then, a heuristic algorithm is developed to locate the optimal or near optimal solutions of the model based on the Tabu search mechanism. Finally, the experimental case is presented to demonstrate the effectiveness of the proposed model and the algorithm.
基金Supported by National Natural Science Foundation of China(Grant Nos.U21B2029 and 51825502).
文摘The meta-heuristic algorithm with local search is an excellent choice for the job-shop scheduling problem(JSP).However,due to the unique nature of the JSP,local search may generate infeasible neighbourhood solutions.In the existing literature,although some domain knowledge of the JSP can be used to avoid infeasible solutions,the constraint conditions in this domain knowledge are sufficient but not necessary.It may lose many feasible solutions and make the local search inadequate.By analysing the causes of infeasible neighbourhood solutions,this paper further explores the domain knowledge contained in the JSP and proposes the sufficient and necessary constraint conditions to find all feasible neighbourhood solutions,allowing the local search to be carried out thoroughly.With the proposed conditions,a new neighbourhood structure is designed in this paper.Then,a fast calculation method for all feasible neighbourhood solutions is provided,significantly reducing the calculation time compared with ordinary methods.A set of standard benchmark instances is used to evaluate the performance of the proposed neighbourhood structure and calculation method.The experimental results show that the calculation method is effective,and the new neighbourhood structure has more reliability and superiority than the other famous and influential neighbourhood structures,where 90%of the results are the best compared with three other well-known neighbourhood structures.Finally,the result from a tabu search algorithm with the new neighbourhood structure is compared with the current best results,demonstrating the superiority of the proposed neighbourhood structure.
文摘In this paper, we propose a new genetic algorithm for job-shop scheduling problems （JSP）. The proposed method uses the operation-based representation, based on schema theorem and building block hypothesis, a new crossover is proposed ： By selecting short, low order highly fit schemas to genetic operator, the crossover can exchange meaningful ordering information of parents effectively and can search the global optimization. Simulation results on MT benchmark problem coded by C ＋ ＋ show that our genetic operators are very powerful and suitable to job-shop scheduling problems and our method outperforms the previous GA-based approaches.
基金supported by the National Natural Science Foundation of China(Nos.U21B2029 and 51825502).
文摘Meta-heuristic algorithms search the problem solution space to obtain a satisfactory solution within a reasonable timeframe.By combining domain knowledge of the specific optimization problem,the search efficiency and quality of meta-heuristic algorithms can be significantly improved,making it crucial to identify and summarize domain knowledge within the problem.In this paper,we summarize and analyze domain knowledge that can be applied to meta-heuristic algorithms in the job-shop scheduling problem(JSP).Firstly,this paper delves into the importance of domain knowledge in optimization algorithm design.After that,the development of different methods for the JSP are reviewed,and the domain knowledge in it for meta-heuristic algorithms is summarized and classified.Applications of this domain knowledge are analyzed,showing it is indispensable in ensuring the optimization performance of meta-heuristic algorithms.Finally,this paper analyzes the relationship among domain knowledge,optimization problems,and optimization algorithms,and points out the shortcomings of the existing research and puts forward research prospects.This paper comprehensively summarizes the domain knowledge in the JSP,and discusses the relationship between the optimization problems,optimization algorithms and domain knowledge,which provides a research direction for the metaheuristic algorithm design for solving the JSP in the future.
基金supported in part by the National Natural Science Foundation of China under Grant No.52175490.
文摘The shop scheduling problem with limited buffers has broad applications in real-world production scenarios,so this research direction is of great practical significance.However,there is currently little research on the hybrid flow shop scheduling problem with limited buffers(LBHFSP).This paper deeply investigates the LBHFSP to optimize the goal of the total completion time.To better solve the LBHFSP,a multi-level subpopulation-based particle swarm optimization algorithm(MLPSO)is proposed,which is founded on the attributes of the LBHFSP and the shortcomings of the basic PSO(particle swarm optimization)algorithm.In MLPSO,firstly,considering the impact of the limited buffers on the process of subsequent operations,a specific circular decoding strategy is developed to accommodate the characteristics of limited buffers.Secondly,an initialization strategy based on blocking time is designed to enhance the quality and diversity of the initial population.Afterward,a multi-level subpopulation collaborative search is developed to prevent being trapped in a local optimum and improve the global exploration capability.Additionally,a local search strategy based on the first blocked job is designed to enhance the MLPSO algorithm’s exploitation capability.Lastly,numerous experiments are carried out to test the performance of the proposed MLPSO by comparing it with classical intelligent optimization and popular algorithms in recent years.The results confirm that the proposed MLPSO has an outstanding performance when compared to other algorithms when solving LBHFSP.
文摘With the development of economic globalization,distributedmanufacturing is becomingmore andmore prevalent.Recently,integrated scheduling of distributed production and assembly has captured much concern.This research studies a distributed flexible job shop scheduling problem with assembly operations.Firstly,a mixed integer programming model is formulated to minimize the maximum completion time.Secondly,a Q-learning-assisted coevolutionary algorithmis presented to solve themodel:(1)Multiple populations are developed to seek required decisions simultaneously;(2)An encoding and decoding method based on problem features is applied to represent individuals;(3)A hybrid approach of heuristic rules and random methods is employed to acquire a high-quality population;(4)Three evolutionary strategies having crossover and mutation methods are adopted to enhance exploration capabilities;(5)Three neighborhood structures based on problem features are constructed,and a Q-learning-based iterative local search method is devised to improve exploitation abilities.The Q-learning approach is applied to intelligently select better neighborhood structures.Finally,a group of instances is constructed to perform comparison experiments.The effectiveness of the Q-learning approach is verified by comparing the developed algorithm with its variant without the Q-learning method.Three renowned meta-heuristic algorithms are used in comparison with the developed algorithm.The comparison results demonstrate that the designed method exhibits better performance in coping with the formulated problem.
基金This project is supported by National Natural Science Foundation of China (No.70071017).
文摘A new heuristic algorithm is proposed for the problem of finding the minimummakespan in the job-shop scheduling problem. The new algorithm is based on the principles ofparticle swarm optimization (PSO). PSO employs a collaborative population-based search, which isinspired by the social behavior of bird flocking. It combines local search (by self experience) andglobal search (by neighboring experience), possessing high search efficiency. Simulated annealing(SA) employs certain probability to avoid becoming trapped in a local optimum and the search processcan be controlled by the cooling schedule. By reasonably combining these two different searchalgorithms, a general, fast and easily implemented hybrid optimization algorithm, named HPSO, isdeveloped. The effectiveness and efficiency of the proposed PSO-based algorithm are demonstrated byapplying it to some benchmark job-shop scheduling problems and comparing results with otheralgorithms in literature. Comparing results indicate that PSO-based algorithm is a viable andeffective approach for the job-shop scheduling problem.
基金the financial support of the National Key Research and Development Plan(2021YFB3302501)the financial support of the National Natural Science Foundation of China(12102077)。
文摘Safe and efficient sortie scheduling on the confined flight deck is crucial for maintaining high combat effectiveness of the aircraft carrier.The primary difficulty exactly lies in the spatiotemporal coordination,i.e.,allocation of limited supporting resources and collision-avoidance between heterogeneous dispatch entities.In this paper,the problem is investigated in the perspective of hybrid flow-shop scheduling problem by synthesizing the precedence,space and resource constraints.Specifically,eight processing procedures are abstracted,where tractors,preparing spots,catapults,and launching are virtualized as machines.By analyzing the constraints in sortie scheduling,a mixed-integer planning model is constructed.In particular,the constraint on preparing spot occupancy is improved to further enhance the sortie efficiency.The basic trajectory library for each dispatch entity is generated and a delayed strategy is integrated to address the collision-avoidance issue.To efficiently solve the formulated HFSP,which is essentially a combinatorial problem with tightly coupled constraints,a chaos-initialized genetic algorithm is developed.The solution framework is validated by the simulation environment referring to the Fort-class carrier,exhibiting higher sortie efficiency when compared to existing strategies.And animation of the simulation results is available at www.bilibili.com/video/BV14t421A7Tt/.The study presents a promising supporting technique for autonomous flight deck operation in the foreseeable future,and can be easily extended to other supporting scenarios,e.g.,ammunition delivery and aircraft maintenance.
文摘The standard genetic algorithm has limitations of a low convergence rate and premature convergence in solving the job-shop scheduling problem.To overcome these limitations,this paper presents a new improved hybrid genetic algorithm on the basis of the idea of graft in botany.Through the introduction of a grafted population and crossover probability matrix,this algorithm accelerates the convergence rate greatly and also increases the ability to fight premature convergence.Finally,the approach is tested on a set of standard instances taken from the literature and compared with other approaches.The computation results validate the effectiveness of the proposed algorithm.
基金This research was supported in part by the National Key Research and Development Program of China under Grant 2022YFB3305303in part by the National Natural Science Foundations of China(NSFC)under Grant 62106055+1 种基金in part by the Guangdong Natural Science Foundation under Grant 2022A1515011825in part by the Guangzhou Science and Technology Planning Project under Grants 2023A04J0388 and 2023A03J0662.
文摘Marine container terminal(MCT)plays a key role in the marine intelligent transportation system and international logistics system.However,the efficiency of resource scheduling significantly influences the operation performance of MCT.To solve the practical resource scheduling problem(RSP)in MCT efficiently,this paper has contributions to both the problem model and the algorithm design.Firstly,in the problem model,different from most of the existing studies that only consider scheduling part of the resources in MCT,we propose a unified mathematical model for formulating an integrated RSP.The new integrated RSP model allocates and schedules multiple MCT resources simultaneously by taking the total cost minimization as the objective.Secondly,in the algorithm design,a pre-selection-based ant colony system(PACS)approach is proposed based on graphic structure solution representation and a pre-selection strategy.On the one hand,as the RSP can be formulated as the shortest path problem on the directed complete graph,the graphic structure is proposed to represent the solution encoding to consider multiple constraints and multiple factors of the RSP,which effectively avoids the generation of infeasible solutions.On the other hand,the pre-selection strategy aims to reduce the computational burden of PACS and to fast obtain a higher-quality solution.To evaluate the performance of the proposed novel PACS in solving the new integrated RSP model,a set of test cases with different sizes is conducted.Experimental results and comparisons show the effectiveness and efficiency of the PACS algorithm,which can significantly outperform other state-of-the-art algorithms.
基金supported by the National Natural Science Foundation of China (Grant Nos. 51075337, 50705076, 50705077)the Natural Sci-ence Basic Research Plan in Shaanxi Province of China (Grant No. 2009JQ9002)
文摘Job-shop scheduling problem with discretely controllable processing times (JSP-DCPT) is modeled based on the disjunctive graph, and the formulation of JSP-DCPT is presented. A three-step decomposition approach is proposed so that JSP-DCPT can be handled by solving a job-shop scheduling problem (JSP) and a series of discrete time-cost tradeoff problems. To simplify the decomposition approach, the time-cost phase plane is introduced to describe tradeoffs of the discrete time-cost tradeoff problem, and an extreme mode-based set dominant theory is elaborated so that an upper bound is determined to cut discrete time-cost tradeoff problems generated by using the proposed decomposition approach. An extreme mode-based set dominant decomposition algorithm (EMSDDA) is then proposed. Experimental simulations for instance JSPDCPT_FT10, which is designed based on a JSP benchmark FT10, demonstrate the effectiveness of the proposed theory and the decomposition approach.
基金This work was supported by the National Natural Science Foundation of China(Nos.61973120,62076095,61673175,and 61573144).
文摘Economic globalization has transformed many manufacturing enterprises from a single-plant production mode to a multi-plant cooperative production mode.The distributed flexible job-shop scheduling problem(DFJSP)has become a research hot topic in the field of scheduling because its production is closer to reality.The research of DFJSP is of great significance to the organization and management of actual production process.To solve the heterogeneous DFJSP with minimal completion time,a hybrid chemical reaction optimization(HCRO)algorithm is proposed in this paper.Firstly,a novel encoding-decoding method for flexible manufacturing unit(FMU)is designed.Secondly,half of initial populations are generated by scheduling rule.Combined with the new solution acceptance method of simulated annealing(SA)algorithm,an improved method of critical-FMU is designed to improve the global and local search ability of the algorithm.Finally,the elitist selection strategy and the orthogonal experimental method are introduced to the algorithm to improve the convergence speed and optimize the algorithm parameters.In the experimental part,the effectiveness of the simulated annealing algorithm and the critical-FMU refinement methods is firstly verified.Secondly,in the comparison with other existing algorithms,the proposed optimal scheduling algorithm is not only effective in homogeneous FMUs examples,but also superior to existing algorithms in heterogeneous FMUs arithmetic cases.
基金supported by the National Key Research and Development Program of China (No.2020YFB1710500)the National Natural Science Foundation of China(No.51805253)the Fundamental Research Funds for the Central Universities(No. NP2020304)
文摘The flexible job-shop scheduling problem(FJSP)with combined processing constraints is a common scheduling problem in mixed-flow production lines.However,traditional methods for classic FJSP cannot be directly applied.Targeting this problem,the process state model of a mixed-flow production line is analyzed.On this basis,a mathematical model of a mixed-flow job-shop scheduling problem with combined processing constraints is established based on the traditional FJSP.Then,an improved genetic algorithm with multi-segment encoding,crossover,and mutation is proposed for the mixed-flow production line problem.Finally,the proposed algorithm is applied to the production workshop of missile structural components at an aerospace institute to verify its feasibility and effectiveness.
文摘The fuzzy goal flexible job-shop scheduling problem （FGFJSP） is the extension of FJSP. Compared with the convention JSP, it can solve the fuzzy goal problem and meet suit requirements of the key job. The multi-object problem, such as the fuzzy cost, the fuzzy due-date, and the fuzzy makespan, etc, can be solved by FGFJSP. To optimize FGFJSP, an individual optimization and colony diversity genetic algorithm （IOCDGA） is presented to accelerate the convergence speed and to avoid the earliness. In IOCDGA, the colony average distance and the colony entropy are defined after the definition of the encoding model. The colony diversity is expressed by the colony average distance and the colony entropy. The crossover probability and the mutation probability are controlled by the colony diversity. The evolution emphasizes that sigle individual or a few individuals evolve into the best in IOCDGA, but not the all in classical GA. Computational results show that the algorithm is applicable and the number of iterations is less.
文摘In the flexible job-shop scheduling problem （FJSP）, each operation has to be assigned to a machine from a set of capable machines before alocating the assigned operations on all machines. To solve the multi-objective FJSP, the Grantt graph oriented string representation （GOSR） and the basic manipulation of the genetic algorithm operator are presented. An integrated operator genetic algorithm （IOGA） and its process are described. Comparison between computational results and the latest research shows that the proposed algorithm is effective in reducing the total workload of all machines, the makespan and the critical machine workload.
