运筹与管理2025，Vol.34Issue(7)：32-39,8.DOI:10.12005/orms.2025.0204
考虑自动导引车充电的多目标作业车间调度问题
Multi-objective Job Shop Scheduling Problem Considering Automatic Guided Vehicles Recharging
摘要
Abstract
The application of automated guided vehicles(AGV)in production systems has undeniably enhanced production efficiency.They play a crucial role in transporting raw materials,components,semi-finished products,and finished products between workstations.With their notable efficiency,ability to work in parallel,and commitment to safety and environmental standards,AGVs not only streamline material handling processes but also alleviate the burden on workers,improve productivity,and reduce labor costs for businesses.However,AGV also bring some practical challenges,such as production delays resulting from inadequate electricity supply. This paper focuses on addressing the multi-objective job shop scheduling problem considering AGV rechar-ging.The problem involves determining the processing and transportation sequence,allocating AGVs,and deter-mining charging time as well as duration.The objectives are to minimize both the makespan and the total electricity consumption.To address this problem,we develop a bi-objective mixed-integer linear programming model,which characterizes the dynamic charging of AGVs.We then develop a dynamic computation resources allocation based MOEA/D to solve the problem.The algorithm designs a two-segment encoding method based on operations and AGV to represent solutions.The first segment includes information about the sequence and priority weights of operations,while the second segment contains information about the allocation and recharging of AGV.To achieve effective allocation of AGV and trade-off of objectives,two heuristic rules considering makespan and electricity consumption are designed.The first heuristic rule considers the number of operations transported by AGV and their corresponding electricity consumption,while the second heuristic rule emphasizes the punctuality of AGV arriving at machines,along with their electricity consumption. We further develop a priority weight-based inserting method to generate high-quality solutions.The priority weights provide precedence constraints between operations and are capable of executing a mapping from continu-ous space to discrete one.To address the issue of overcharging for AGV while minimizing the maximum comple-tion time,this paper proposes a dynamic charging adjustment strategy.Building upon the existing scheme,this strategy adjusts the required electricity for each AGV to match the actual power consumption,thus minimizing the charging time and enabling an earlier start for operations transportation.To promote information sharing,improve the diversity and convergence of the population,the proposed algorithm designs a computation resource-based selection operator,a multiple individual-based crossover operator,a local search-based mutation operator,and a dynamic computational resource allocation strategy.The computation resource-based selection operator determines the source of parents using the computation resources of individuals,thus enhancing the algorithm's exploration and exploitation capabilities.The multiple individual-based crossover operator calculates probabilities for decoding orders of each operation,as well as the assignment of AGV accordingly.The required information for each offspring's gene is determined using a roulette wheel method.The local search-based mutation operator generates multiple excellent offspring by exchanging the priority weights of operations and the assignment of AGV.The dynamic computational resources allocation strategy focuses on allocating more computational resources to promising individuals. The effectiveness of the two heuristic rules and the dynamic recharging strategy,as well as the proposed algorithm,is validated through 35 benchmark instances.We use set coverage and inverted generational distance as indicators to assess the performance of the algorithm.The results obtained from running the program ten times consecutively demonstrate the effectiveness of our proposed algorithm.Additionally,the comparative results of solution times demonstrate that our algorithm exhibits faster performance than other two algorithms.We further display the Pareto sets of some benchmark instances.According to our investigation,some valuable managerial insights for managers are concluded as follows:First,managers should develop charging plans based on the actu-al power consumption of AGV,ensuring timely recharging without compromising production.Second,managers should schedule machining operations during this time to ensure concurrent charging and processing tasks in the production system,thus improving production efficiency.Lastly,we encourage managers to apply the proposed algorithm to practical production due to its effectiveness of optimizing the completion time and total power consumption through effective scheduling of operations and AGV charging.In the future,we will continue to investigate practical production problems,such as AGV scheduling considering machine failures,AGV schedu-ling under carbon emission constraints,and integrated scheduling of AGV and workers.Additionally,we aim to improve existing multi-objective optimization algorithms and enrich the optimization algorithms for job shop sched-uling problems.关键词
作业车间调度/多目标/自动导引车/动态充电/进化操作Key words
job shop scheduling/multi-objective/AGV/dynamic recharging/evolutionary operators分类
信息技术与安全科学引用本文复制引用
张博涵,车阿大,左天帅..考虑自动导引车充电的多目标作业车间调度问题[J].运筹与管理,2025,34(7):32-39,8.基金项目
国家自然科学基金资助项目(71871183,71901176) （71871183,71901176）
