Pareto-Based Complete Local Search and Combined Timetabling for Multi-objective Job Shop Scheduling Problem with No-Wait Constraint

Job shop scheduling has become the basis and core of advanced manufacturing technology. Various differences exist between academic research and practical production. The majority of previous researches on job shop scheduling problem (JSSP)describe the basic production environment, which have a single objective and limited constraints. However,a practical process of production is characterized by having multiple objectives,no-wait constraint,and limited storage. Thus this research focused on multiobjective,no-wait JSSP. To analyze the problem,it was further divided into two sub-problems, namely, sequencing and timetabling. Hybrid non-order strategy and modified complete local search with memory were used to solve each problem individually. A Pareto-based strategy for performing fitness assessment was presented in this study. Various experiments on benchmark problems proved the feasibility and effectiveness of the proposed algorithm.

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.

Strengthened Dominance Relation NSGA-Ⅲ Algorithm Based on Differential Evolution to Solve Job Shop Scheduling Problem

The job shop scheduling problem is a classical combinatorial optimization challenge frequently encountered in manufacturing systems.It involves determining the optimal execution sequences for a set of jobs on various machines to maximize production efficiency and meet multiple objectives.The Non-dominated Sorting Genetic Algorithm Ⅲ(NSGA-Ⅲ)is an effective approach for solving the multi-objective job shop scheduling problem.Nevertheless,it has some limitations in solving scheduling problems,including inadequate global search capability,susceptibility to premature convergence,and challenges in balancing convergence and diversity.To enhance its performance,this paper introduces a strengthened dominance relation NSGA-Ⅲ algorithm based on differential evolution(NSGA-Ⅲ-SD).By incorporating constrained differential evolution and simulated binary crossover genetic operators,this algorithm effectively improves NSGA-Ⅲ’s global search capability while mitigating pre-mature convergence issues.Furthermore,it introduces a reinforced dominance relation to address the trade-off between convergence and diversity in NSGA-Ⅲ.Additionally,effective encoding and decoding methods for discrete job shop scheduling are proposed,which can improve the overall performance of the algorithm without complex computation.To validate the algorithm’s effectiveness,NSGA-Ⅲ-SD is extensively compared with other advanced multi-objective optimization algorithms using 20 job shop scheduling test instances.The experimental results demonstrate that NSGA-Ⅲ-SD achieves better solution quality and diversity,proving its effectiveness in solving the multi-objective job shop scheduling problem.

A Novel Collaborative Evolutionary Algorithm with Two-Population for Multi-Objective Flexible Job Shop Scheduling

Job shop scheduling(JS)is an important technology for modern manufacturing.Flexible job shop scheduling(FJS)is critical in JS,and it has been widely employed in many industries,including aerospace and energy.FJS enables any machine from a certain set to handle an operation,and this is an NP-hard problem.Furthermore,due to the requirements in real-world cases,multi-objective FJS is increasingly widespread,thus increasing the challenge of solving the FJS problems.As a result,it is necessary to develop a novel method to address this challenge.To achieve this goal,a novel collaborative evolutionary algorithmwith two-population based on Pareto optimality is proposed for FJS,which improves the solutions of FJS by interacting in each generation.In addition,several experimental results have demonstrated that the proposed method is promising and effective for multi-objective FJS,which has discovered some new Pareto solutions in the well-known benchmark problems,and some solutions can dominate the solutions of some other methods.

An Improved Harris Hawk Optimization Algorithm for Flexible Job Shop Scheduling Problem

Flexible job shop scheduling problem(FJSP)is the core decision-making problem of intelligent manufacturing production management.The Harris hawk optimization(HHO)algorithm,as a typical metaheuristic algorithm,has been widely employed to solve scheduling problems.However,HHO suffers from premature convergence when solving NP-hard problems.Therefore,this paper proposes an improved HHO algorithm(GNHHO)to solve the FJSP.GNHHO introduces an elitism strategy,a chaotic mechanism,a nonlinear escaping energy update strategy,and a Gaussian random walk strategy to prevent premature convergence.A flexible job shop scheduling model is constructed,and the static and dynamic FJSP is investigated to minimize the makespan.This paper chooses a two-segment encoding mode based on the job and the machine of the FJSP.To verify the effectiveness of GNHHO,this study tests it in 23 benchmark functions,10 standard job shop scheduling problems(JSPs),and 5 standard FJSPs.Besides,this study collects data from an agricultural company and uses the GNHHO algorithm to optimize the company’s FJSP.The optimized scheduling scheme demonstrates significant improvements in makespan,with an advancement of 28.16%for static scheduling and 35.63%for dynamic scheduling.Moreover,it achieves an average increase of 21.50%in the on-time order delivery rate.The results demonstrate that the performance of the GNHHO algorithm in solving FJSP is superior to some existing algorithms.

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.

An improved multi-objective optimization algorithm for solving flexible job shop scheduling problem with variable batches

In order to solve the flexible job shop scheduling problem with variable batches,we propose an improved multiobjective optimization algorithm,which combines the idea of inverse scheduling.First,a flexible job shop problem with the variable batches scheduling model is formulated.Second,we propose a batch optimization algorithm with inverse scheduling in which the batch size is adjusted by the dynamic feedback batch adjusting method.Moreover,in order to increase the diversity of the population,two methods are developed.One is the threshold to control the neighborhood updating,and the other is the dynamic clustering algorithm to update the population.Finally,a group of experiments are carried out.The results show that the improved multi-objective optimization algorithm can ensure the diversity of Pareto solutions effectively,and has effective performance in solving the flexible job shop scheduling problem with variable batches.

Research on Flexible Job Shop Scheduling Optimization Based on Segmented AGV

As a typical transportation tool in the intelligent manufacturing system,Automatic Guided Vehicle(AGV)plays an indispensable role in the automatic production process of the workshop.Therefore,integrating AGV resources into production scheduling has become a research hotspot.For the scheduling problem of the flexible job shop adopting segmented AGV,a dual-resource scheduling optimization mathematical model of machine tools and AGVs is established by minimizing the maximum completion time as the objective function,and an improved genetic algorithmis designed to solve the problem in this study.The algorithmdesigns a two-layer codingmethod based on process coding and machine tool coding and embeds the task allocation of AGV into the decoding process to realize the real dual resource integrated scheduling.When initializing the population,three strategies are designed to ensure the diversity of the population.In order to improve the local search ability and the quality of the solution of the genetic algorithm,three neighborhood structures are designed for variable neighborhood search.The superiority of the improved genetic algorithmand the influence of the location and number of transfer stations on scheduling results are verified in two cases.

Job-shop Scheduling with Multi-objectives Based on Genetic Algorithms

The technology of production planning and scheduling is one of the critical technologies that decide whether the automated manufacturing systems can get the expected economy. Job shop scheduling belongs to the special class of NP-hard problems. Most of the algorithms used to optimize this class of problems have an exponential time; that is, the computation time increases exponentially with problem size. In scheduling study, makespan is often considered as the main objective. In this paper, makespan, the due date request of the key jobs, the availability of the key machine, the average wait-time of the jobs, and the similarities between the jobs and so on are taken into account based on the application of mechanical engineering. The job shop scheduling problem with multi-objectives is analyzed and studied by using genetic algorithms based on the mechanics of genetics and natural selection. In this research, the tactics of the coding and decoding and the design of the genetic operators, along with the description of the mathematic model of the multi-objective functions, are presented. Finally an illu-strative example is given to testify the validity of this algorithm.

EFFICIENT MULTI-OBJECTIVE EVOLUTIONARY ALGORITHM FOR JOB SHOP SCHEDULING

A new representation method is first presented based on priority roles. According to this method, each entry in the chromosome indicates that in the procedure of the Giffler and Thompson （GT） algorithm, the conflict occurring in the corresponding machine is resolved by the corresponding priority role. Then crowding-measure multi-objective evolutionary algorithm （CMOEA） is designed, in which both archive maintenance and fitness assignment use crowding measure. Finally the comparisons between CMOEA and SPEA in solving 15 scheduling problems demonstrate that CMOEA is suitable to job shop scheduling.

An Effective Neighborhood Solution Clipping Method for Large-Scale Job Shop Scheduling Problem

The job shop scheduling problem(JSSP)is a classical combinatorial optimization problem that exists widely in diverse scenarios of manufacturing systems.It is a well-known NP-hard problem,when the number of jobs increases,the difficulty of solving the problem exponentially increases.Therefore,a major challenge is to increase the solving efficiency of current algorithms.Modifying the neighborhood structure of the solutions can effectively improve the local search ability and efficiency.In this paper,a genetic Tabu search algorithm with neighborhood clipping(GTS_NC)is proposed for solving JSSP.A neighborhood solution clipping method is developed and embedded into Tabu search to improve the efficiency of the local search by clipping the search actions of unimproved neighborhood solutions.Moreover,a feasible neighborhood solution determination method is put forward,which can accurately distinguish feasible neighborhood solutions from infeasible ones.Both of the methods are based on the domain knowledge of JSSP.The proposed algorithmis compared with several competitive algorithms on benchmark instances.The experimental results show that the proposed algorithm can achieve superior results compared to other competitive algorithms.According to the numerical results of the experiments,it is verified that the neighborhood solution clippingmethod can accurately identify the unimproved solutions and reduces the computational time by at least 28%.

Applying Job Shop Scheduling to SMEs Manufacturing Platform to Revitalize B2B Relationship

A small and medium enterprises(SMEs)manufacturing platform aims to perform as a significant revenue to SMEs and vendors by providing scheduling and monitoring capabilities.The optimal job shop scheduling is generated by utilizing the scheduling system of the platform,and a minimum production time,i.e.,makespan decides whether the scheduling is optimal or not.This scheduling result allows manufacturers to achieve high productivity,energy savings,and customer satisfaction.Manufacturing in Industry 4.0 requires dynamic,uncertain,complex production environments,and customer-centered services.This paper proposes a novel method for solving the difficulties of the SMEs manufacturing by applying and implementing the job shop scheduling system on a SMEs manufacturing platform.The primary purpose of the SMEs manufacturing platform is to improve the B2B relationship between manufacturing companies and vendors.The platform also serves qualified and satisfactory production opportunities for buyers and producers by meeting two key factors:early delivery date and fulfillment of processing as many orders as possible.The genetic algorithm(GA)-based scheduling method results indicated that the proposed platform enables SME manufacturers to obtain optimized schedules by solving the job shop scheduling problem(JSSP)by comparing with the real-world data from a textile weaving factory in South Korea.The proposed platform will provide producers with an optimal production schedule,introduce new producers to buyers,and eventually foster relationships and mutual economic interests.

SOLVING FLEXIBLE JOB SHOP SCHEDULING PROBLEM BY GENETIC ALGORITHM

The job shop scheduli ng problem has been studied for decades and known as an NP-hard problem. The fl exible job shop scheduling problem is a generalization of the classical job sche duling problem that allows an operation to be processed on one machine out of a set of machines. The problem is to assign each operation to a machine and find a sequence for the operations on the machine in order that the maximal completion time of all operations is minimized. A genetic algorithm is used to solve the f lexible job shop scheduling problem. A novel gene coding method aiming at job sh op problem is introduced which is intuitive and does not need repairing process to validate the gene. Computer simulations are carried out and the results show the effectiveness of the proposed algorithm.

Infeasibility test algorithm and fast repair algorithm of job shop scheduling problem

To diagnose the feasibility of the solution of a job-shop scheduling problem（JSSP）,a test algorithm based on diagraph and heuristic search is developed and verified through a case study.Meanwhile,a new repair algorithm for modifying an infeasible solution of the JSSP to become a feasible solution is proposed for the general JSSP.The computational complexity of the test algorithm and the repair algorithm is both O（n） under the worst-case scenario,and O（2J＋M） for the repair algorithm under the best-case scenario.The repair algorithm is not limited to specific optimization methods,such as local tabu search,genetic algorithms and shifting bottleneck procedures for job shop scheduling,but applicable to generic infeasible solutions for the JSSP to achieve feasibility.

具有模糊加工时间的Flexible Job-Shop Scheduling问题的研究

采用梯形模糊数来表征柔性生产系统中的时间参数,并在此基础上对具有模糊加工时间的柔性作业车间最小化制造跨度调度问题进行了描述。然后给出了基于粒子群优化的柔性作业车间调度模型。最后通过实例验证了模型的有效性。

Project Scheduling问题和Job-Shop问题的神经网络解

Project Scheduling问题和Job-Shop问题是著名的NP难题。本文用神经网络方法去解这两个问题,软件模拟结果是令人满意的。这种方法也为解一大类组合优化问题提供了一个新的途径。

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.

A Review on Swarm Intelligence and Evolutionary Algorithms for Solving Flexible Job Shop Scheduling Problems

Flexible job shop scheduling problems(FJSP)have received much attention from academia and industry for many years.Due to their exponential complexity,swarm intelligence(SI)and evolutionary algorithms(EA)are developed,employed and improved for solving them.More than 60%of the publications are related to SI and EA.This paper intents to give a comprehensive literature review of SI and EA for solving FJSP.First,the mathematical model of FJSP is presented and the constraints in applications are summarized.Then,the encoding and decoding strategies for connecting the problem and algorithms are reviewed.The strategies for initializing algorithms?population and local search operators for improving convergence performance are summarized.Next,one classical hybrid genetic algorithm(GA)and one newest imperialist competitive algorithm(ICA)with variables neighborhood search(VNS)for solving FJSP are presented.Finally,we summarize,discus and analyze the status of SI and EA for solving FJSP and give insight into future research directions.

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.

Emergency Local Searching Approach for Job Shop Scheduling

Existing methods of local search mostly focus on how to reach optimal solution.However,in some emergency situations,search time is the hard constraint for job shop scheduling problem while optimal solution is not necessary.In this situation,the existing method of local search is not fast enough.This paper presents an emergency local search(ELS) approach which can reach feasible and nearly optimal solution in limited search time.The ELS approach is desirable for the aforementioned emergency situations where search time is limited and a nearly optimal solution is sufficient,which consists of three phases.Firstly,in order to reach a feasible and nearly optimal solution,infeasible solutions are repaired and a repair technique named group repair is proposed.Secondly,in order to save time,the amount of local search moves need to be reduced and this is achieved by a quickly search method named critical path search(CPS).Finally,CPS sometimes stops at a solution far from the optimal one.In order to jump out the search dilemma of CPS,a jump technique based on critical part is used to improve CPS.Furthermore,the schedule system based on ELS has been developed and experiments based on this system completed on the computer of Intel Pentium(R) 2.93 GHz.The experimental result shows that the optimal solutions of small scale instances are reached in 2 s,and the nearly optimal solutions of large scale instances are reached in 4 s.The proposed ELS approach can stably reach nearly optimal solutions with manageable search time,and can be applied on some emergency situations.