Research On The Algorithm Of Zero Idle Workshop Scheduling Proble

Production scheduling,as a core component and key technology in the management a nd control of manufacturing enterprises’production planning,is playing an increasingly im portant role.The production scheduling problem involves the decision-making process of a llocating limited resources to different tasks,with the aim of optimizing one or more object ives.It is widely present in most workshop manufacturing and production systems today.O ptimized production scheduling can improve production efficiency,reduce production cost s,and bring better economic and social benefits to the enterprise.Therefore,effective and r ational scheduling of the production process holds significant significance.From the persp ective of practical applications,scheduling optimization faces challenges such as strong co nstraints,high parallelism,large-scale operations,and uncertainties.Both problem modelin g and algorithmic solution methods are highly challenging research topics.The Flowshop Scheduling Problem(FSP)involves the production process of n jobs o n m machines,where each job needs to pass through the first machine,then the second mac hine,and so on,until the last machine.The goal of the flowshop scheduling problem is to d etermine the job processing sequence on these m machines in order to optimize a given per formance metric.The No-Idle Flowshop Scheduling Problem(NIFSP)assumes that the ma chines operate continuously without any idle time between adjacent jobs.This problem is widely encountered in practical production processes,such as in traditional industries like ceramic block production,glass fiber processing,casting,and integrated circuit manufactur ing.Due to technical requirements or the use of expensive machinery in certain manufactur ing environments,it is not permissible to stop the machine currently processing a job.Ther efore,the trend is to study job sequencing with zero machine idle time to minimize the ma ximum completion time(makespan).The research on this problem focuses on the followin g specific tasks:1.Regarding the widely used heuristic rules NEH and FRB in the classic FSP,resear ch has been conducted on their rule frameworks and the reproduction of solving the no-idle flowshop scheduling problem.While the NEH heuristic rule is computationally efficient,i t is only suitable for small-scale problem instances.For workshop scheduling problems wit h constraints,it exhibits poor optimization quality of the scheduling solutions.On the other hand,the FRB series rules enhance the NEH rule by incorporating a series of local searche s.Although they improve the quality of scheduling solutions,they consume a significant a mount of computational time.When embedded into the algorithm framework,it adversely affects the number of iterations within the algorithm,thus impacting the algorithm’s perfor mance.To address the issues of the NEH and FRB rules,an improved heuristic rule called FRB5_kis proposed.Through independent experiments among heuristic algorithms and com parative experiments by integrating the heuristic algorithms into the classical iterative gree dy algorithm framework for FSP,the optimization of scheduling solutions and the balance between CPU consumption time are evaluated from different dimensions.2.Regarding the no-idle flowshop scheduling problem,research has been conducted on the performance-efficient algorithms in the FSP problem,including the Iterative Greedy algorithm(IG),its variant IGall,the VBIH algorithm,and the HDDE and GVNS algorith ms.By modifying the objective function and reproducing the algorithm framework,the no-idle flowshop scheduling problem is solved.The analysis and summary of experimental da ta reveal that the classic IG algorithm performs well compared to traditional workshop sch eduling algorithms.However,as the workshop problem becomes more complex,it faces co mputational limitations and a noticeable decline in optimization performance when dealing with scheduling problems under the no-idle constraint.The variant algorithm IGall also ex hibits insufficient optimization performance based on the IG algorithm.The VBIH algorith m introduces a new idea of block insertion mode during the disruption phase but lacks suffi cient disruption intensity.The fixed number of removed job blocks limits the algorithm’s fl exibility,leading to inadequate optimization performance in complex no-idle workshop sch eduling problems.Similarly,the HDDE and GVNS algorithms face similar challenges,lac king flexibility in handling complex problem instances and requiring improvement in opti mization performance.3.The proposed improved algorithm,VIIA,incorporates inner and outer iterations in the disruption-reconstruction phase of the algorithm framework to expand the search space.It adapts to different problem sizes using the job block insertion method.Through paramet er tuning experiments,the optimization performance is improved.The NIFSP problem wit h makespan as the objective is solved using five comparative algorithms and the proposed i mproved algorithm.Extensive comparative experiments are conducted to validate the opti mization performance of the improved algorithm in finding scheduling solutions.Through multi-factor analysis,the experimental results are visually compared,and the performance of the improved algorithm is analyzed in conjunction with known optimal results.Based on extensive experimental data,it is observed that the comprehensive performa nce of the improved heuristic rule FRB5_ksurpasses the NEH heuristic algorithm and the F RB series heuristic algorithms.The proposed improved algorithm,VIIA,enhances the qual ity of solutions for the no-idle flowshop scheduling problem and optimizes 91 out of 250 in stances from Ruiz’s benchmark for the no-idle flowshop problem.The average relative per centage of VIIA is 0.23%,compared to the lowest value of 0.31%among the comparative algorithms.Both the optimization performance and comprehensive performance of VIIA o utperform the other five comparative classical algorithms.