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.

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.

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.

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 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.

A Dynamic Job Shop Scheduling Method Based on Ant Colony Coordination System

Due to the stubborn nature of dynamic job shop scheduling problem,a novel ant colony coordination mechanism is proposed in this paper to search for an optimal schedule in dynamic environment.In ant colony coordination mechanism,the dynamic job shop is composed of several autonomous ants.These ants coordinate with each other by simulating the ant foraging behavior of spreading pheromone on the trails,by which they can make information available globally,and further more guide ants make optimal decisions.The proposed mechanism is tested by several instances and the results confirm the validity of it.

ANALYSIS AND IMPROVEMENT OF LEAD TIME FOR JOB SHOP UNDER MIXED PRODUCTION SYSTEM

Firstly an overview of the potential impact on work-in-process （WIP） and lead time is provided when transfer lot sizes are undifferentiated from processing lot sizes. Simple performance examples are compared to those from a shop with one-piece transfer lots. Next, a mathematical programming model for minimizing lead time in the mixed-model job shop is presented, in which one-piece transfer lots are used. Key factors affecting lead time are found by analyzing the sum of the longest setup time of individual items among the shared processes （SLST） and the longest processing time of individual items among processes （LPT）. And lead time can be minimized by cutting down the SLST and LPT. Reduction of the SLST is described as a traveling salesman problem （TSP）, and the minimum of the SLST is solved through job shop scheduling. Removing the bottleneck and leveling the production line optimize the LPT. If the number of items produced is small, the routings are relatively short, and items and facilities are changed infrequently, the optimal schedule will remain valid. Finally a brief example serves to illustrate the method.

基于ACPM和BFSM的动态Job-Shop调度算法

通过对不同时刻开始加工的产品加工树的分解 ,可将产品加工工序分为具有惟一紧前、紧后的相关工序和独立工序 在对这两类工序研究分批综合应用拟关键路径法 (ACPM )和最佳适应调度方法 (BFSM)调度时 ,考虑了关键设备的工序紧凑性 通过分析与实例验证 ,所提出的调度方法对解决动态的Job

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.

一类Job-shop车间生产计划和调度的集成优化

讨论一类Job-shop车间的生产计划和调度的集成优化问题,给出了该问题的非线性混合整数规划模型,并采用混合遗传算法进行求解。该模型利用调度约束来细化生产计划,以保证得到可行的调度解。在混合算法中,利用启发式规则来改善初始解集,并采用分段编码策略将计划和调度解映射为染色体。算例研究表明,该算法对求解该类问题具有很好的效果。

基于混合微粒群优化的多目标柔性Job-shop调度

应用传统方法求解多目标柔性Job-shop调度问题是十分困难的,微粒群优化采用基于种群的搜索方式,融合了局部搜索和全局搜索,具有很高的搜索效率.模拟退火算法使用概率来避免陷入局部最优,整个搜索过程可由冷却表来控制.通过对这两种算法的合理组合,建立了一种快速且易于实现的新的混合优化算法.实例计算以及与其他算法的比较说明,该算法是求解多目标柔性Job-shop调度问题的可行且高效的方法.

基于免疫算法的多目标柔性job-shop调度研究

建立了多目标柔性job-shop调度模型;然后提出了带有保优机制免疫算法,利用免疫记忆、接种疫苗等机制,在算法中保留并充分利用每代最优抗体和局部最优基因,使算法加快收敛;针对这类调度的柔性,提出基于工序设备双层抗体编码方案和基于设备能力空间的解码方案;采用多目标分级评价方法同时对时间、设备和成本等多目标进行评价和优化.最后,用Benchm ark标准问题的仿真和西安航空发动机(集团)有限公司的调度实例验证了算法、策略和调度模型的有效性和优越性.

基于免疫蚁群算法的Job-shop调度问题

描述了作业调度问题,借鉴生物免疫机理提出了求解车间调度问题的免疫蚁群算法,该方法在蚂蚁搜索程中,运用免疫机理提取疫苗,并对进化种群进行免疫操作,从而有效地抑制了蚁群算法的“早熟”和搜索效率低下的问题,显著地提高了蚁群算法对全局最优解的搜索能力和收敛速度,给出了免疫蚁群算法的具体步骤,并对算法进行了实例验证。

免疫遗传算法在柔性Job-shop调度问题中的应用

借鉴生物免疫机理提出了一种求解柔性Job shop车间调度问题的免疫遗传算法.仿真结果表明,该算法有效地避免了传统遗传算法中因选择压力过大造成早熟现象的发生,显著地提高了遗传算法(GA)对全局最优解的搜索能力和收敛速度,这将使遗传算法在众多实际的优化问题上具有更广泛的应用前景.

求解Job-Shop调度问题的多种群双倍体免疫算法研究

Job-Shop调度问题是制造工程学科的NP难题,传统求解方法都有各自的特色和不足。免疫算法是模拟生物免疫系统功能的一种智能优化算法,具有解决复杂工程问题的潜力。针对免疫算法存在的缺陷,提出了多种群双倍体免疫算法,用于求解Job-Shop调度问题。建立了Job-Shop调度问题的数学模型,对典型Job-Shop问题进行了仿真,仿真结果不但验证了它的有效性,而且表明此算法优于其它算法。

求解JobShop调度问题的一种新的邻域搜索算法

利用了混合邻域结构进行搜索来求解JobShop调度问题.算法使用的混合邻域结构不仅使邻域搜索具有效率,而且有助于搜索有效地跳出局部极小值的陷阱,让计算走向前景更好的区域.算法采用的“单机调度”和“同工件工序调整”的跳坑策略能够帮助搜索找到更好的局部极小值.采用国际文献中所有的10工件10机器算例以及另外7个难算例作为本算法的测试实验集,与目前国际上最好的近似算法和另外一种先进算法进行了比较.实算结果验证了算法的寻优性能.

多目标柔性Job Shop调度问题的技术现状和发展趋势

首先概述了多目标柔性Job Shop调度问题的基本概念,包括问题定义、常用假设条件、性能指标和问题的分类,讨论了其复杂性;其次,分别从建模、优化方法和原型系统研究方面综述了其发展过程和研究现状,对一类更加通用的多目标柔性Job Shop问题进行了简单的文献综述;最后指出了现有研究存在的问题与不足,并对未来的发展趋势进行了探讨。