Deep Reinforcement Learning Solves Job-shop Scheduling Problems

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.

Necessary and Sufficient Conditions for Feasible Neighbourhood Solutions in the Local Search of the Job-Shop Scheduling Problem

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.

Solving Job-Shop Scheduling Problem Based on Improved Adaptive Particle Swarm Optimization Algorithm

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.

Modified bottleneck-based heuristic for large-scale job-shop scheduling problems with a single bottleneck

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.

Energy-efficient Approach to Minimizing the Energy Consumption in An Extended Job-shop Scheduling Problem

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.

A bi-objective model for job-shop scheduling problem to minimize both energy consumption and makespan

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.

Solving Job-Shop Scheduling Problems by Genetic Algorithms Based on Building Block Hypothesis

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.

Domain Knowledge Used in Meta-Heuristic Algorithms for the Job-Shop Scheduling Problem:Review and Analysis

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.

A Pre-Selection-Based Ant Colony System for Integrated Resources Scheduling Problem at Marine Container Terminal

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.

APPLYING PARTICLE SWARM OPTIMIZATION TO JOB-SHOPSCHEDULING 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 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.

An adaptive multi-population genetic algorithm for job-shop scheduling problem

Job-shop scheduling problem （JSP） is a typical NP-hard combinatorial optimization problem and has a broad background for engineering application. Nowadays, the effective approach for JSP is a hot topic in related research area of manufacturing system. However, some JSPs, even for moderate size instances, are very difficult to find an optimal solution within a reasonable time because of the process constraints and the complex large solution space. In this paper, an adaptive multi-population genetic algorithm （AMGA） has been proposed to solve this prob- lem. Firstly, using multi-populations and adaptive cross- over probability can enlarge search scope and improve search performance. Secondly, using adaptive mutation probability and elite replacing mechanism can accelerate convergence speed. The approach is tested for some clas- sical benchmark JSPs taken from the literature and com- pared with some other approaches. The computational results show that the proposed AMGA can produce optimal or near-optimal values on almost all tested benchmark instances. Therefore, we can believe that AMGA can be considered as an effective method for solving JSP.

Energy-Saving Distributed Flexible Job Shop Scheduling Optimization with Dual Resource Constraints Based on Integrated Q-Learning Multi-Objective Grey Wolf Optimizer

The distributed flexible job shop scheduling problem(DFJSP)has attracted great attention with the growth of the global manufacturing industry.General DFJSP research only considers machine constraints and ignores worker constraints.As one critical factor of production,effective utilization of worker resources can increase productivity.Meanwhile,energy consumption is a growing concern due to the increasingly serious environmental issues.Therefore,the distributed flexible job shop scheduling problem with dual resource constraints(DFJSP-DRC)for minimizing makespan and total energy consumption is studied in this paper.To solve the problem,we present a multi-objective mathematical model for DFJSP-DRC and propose a Q-learning-based multi-objective grey wolf optimizer(Q-MOGWO).In Q-MOGWO,high-quality initial solutions are generated by a hybrid initialization strategy,and an improved active decoding strategy is designed to obtain the scheduling schemes.To further enhance the local search capability and expand the solution space,two wolf predation strategies and three critical factory neighborhood structures based on Q-learning are proposed.These strategies and structures enable Q-MOGWO to explore the solution space more efficiently and thus find better Pareto solutions.The effectiveness of Q-MOGWO in addressing DFJSP-DRC is verified through comparison with four algorithms using 45 instances.The results reveal that Q-MOGWO outperforms comparison algorithms in terms of solution quality.

A Grafted Genetic Algorithm for the Job-Shop Scheduling Problem

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.

A decomposition approach to job-shop scheduling problem with discretely controllable processing times

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.

Distributed Flexible Job-Shop Scheduling Problem Based on Hybrid Chemical Reaction Optimization Algorithm

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.

An Improved Genetic Algorithm for Solving the Mixed⁃Flow Job⁃Shop Scheduling Problem with Combined Processing Constraints

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.

FLEXIBLE JOB-SHOP SCHEDULING WITH FUZZY GOAL THROUGH IOCDGA

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.

INTEGRATED OPERATOR GENETIC ALGORITHM FOR SOLVING MULTI-OBJECTIVE FLEXIBLE JOB-SHOP SCHEDULING

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.

Job-Shop Scheduling问题的一个快速算法

Job-Shop Scheduling问题是优化组合中一个著名的难题,即使规模不大的算例在计算上也是很棘手的。文章给出了一个性能很好的算法,该算法找到了所计算的16个算例中12个算例的最优解,而且每个算例在一台个人计算机(CPU为赛扬633)上所花的计算时间不超过1分钟。

A Modi ed Iterated Greedy Algorithm for Flexible Job Shop Scheduling Problem

The flexible job shop scheduling problem(FJSP) is considered as an important problem in the modern manufacturing system. It is known to be an NP-hard problem. Most of the algorithms used in solving FJSP problem are categorized as metaheuristic methods. Some of these methods normally consume more CPU time and some other methods are more complicated which make them di cult to code and not easy to reproduce. This paper proposes a modified iterated greedy(IG) algorithm to deal with FJSP problem in order to provide a simpler metaheuristic, which is easier to code and to reproduce than some other much more complex methods. This is done by separating the classical IG into two phases. Each phase is used to solve a sub-problem of the FJSP: sequencing and routing sub-problems. A set of dispatching rules are employed in the proposed algorithm for the sequencing and machine selection in the construction phase of the solution. To evaluate the performance of proposed algorithm, some experiments including some famous FJSP benchmarks have been conducted. By compared with other algorithms, the experimental results show that the presented algorithm is competitive and able to find global optimum for most instances. The simplicity of the proposed IG provides an e ective method that is also easy to apply and consumes less CPU time in solving the FJSP problem.