具有安装时间的置换流水车间组合干扰管理研究

Combinational disruption management in permutation flow shops with sequence-dependent setup times

针对安装时间与次序相关的置换流水车间环境,研究随机机器故障、加工时间改变、安装时间改变、工件优先级提高、新工件到达、工件取消加工六类常见干扰事件部分或者全部组合发生情况下,考虑初始目标最大完工时间和扰动目标次序变动总量的干扰管理问题。经分析,该问题为NP难问题。通过改进初始种群构建策略以及全局搜索和局部搜索间权衡策略,提出改进文化基因算法对该问题进行求解。最后设计随机干扰算例,分别在初始种群改进前后同经典的NSGA-II算法进行对比,结果验证了本文所提初始种群构建策略和改进文化基因算法在应对不同组合干扰事件和不同问题规模下的有效性。

The flow shop scheduling problem,as one that can be widely abstracted in the actual production and processing environment,is common in manufacturing and service areas such as metallurgy,food processing,and surgical scheduling.Although relatively rich theoretical research results have been achieved,most of these developed solutions are difficult to apply to production practices.A key issue is that most flow shop scheduling research to date ignores the impact of various disruption events in the actual production process.As such,the problem of flow shop disruption management has gradually attracted widespread attention.In recent years,some researchers have begun to consider approaching their analysis from the point of a single disruption event in a flow shop environment.However,in most practical situations,multiple disruption events occur in combination.The processing of such situations is more complicated than for those involving a single disruption event,and in this case,may have a greater impact on the current scheduling scheme.Some researchers have put forward combinational disruption management as a very important research focus and have started to carry out corresponding analysis.However,relative to the number of studies that do not take disruption events into consideration,the body of scheduling research with a focus on combinational disruption events is inadequate.In addition,most of the existing research on disruption management in permutation flow shops assumes that setup time is negligible,or otherwise factored into the processing time.Where the setup time is relatable to the setup sequence,it will have an impact on the scheduling results that cannot be ignored.Finally,most of the existing body of disruption management research tackles single-objective problems,or converts multi-objective problems to single-objective ones through a linear weighted method,while neglecting the impact of the trade-off between the initial objective and the disruption objective in the disruption management problem.In light of the various deficiencies within the existing body of research,this paper studies six types of common disruption events:random machine failure,processing time variation,setup time variation,job priority update,new job arrival,and job cancellation,in a permutation flow shop environment where setup time and sequence are relevant factors.Disruption management problems are framed as a consequence of either partially or fully combinational events.In order to meet the preferences of different decision makers,in reference to the existing literature on the treatment of various disruption events,we are committed to simultaneously minimizing the initial objective(make span)and the disruption objective(sequence deviation)to better performance and obtain a Pareto optimal solution.After analysis,this problem appeared to be difficult to solve.However,we proposed an improved memetic algorithm to solve it.Based on our memetic algorithm,we implemented an initial population construction strategy.First,the optimal population under two single objectives is obtained by minimizing the initial objective and the disruption objective by sorting using a non-dominant sorting method,and then selecting the individuals who reign superior after the non-dominant ones are selected out.Second,the remaining initial population is supplemented with randomly generated individuals to construct a final initial population.For some key elements of local search(such as the selection of objective individuals or the criteria for receiving new individuals),the characteristics of the problem and the algorithm are further analyzed to determine the appropriate processing method that will allow the algorithm to better meet the problem-solving requirements.Finally,the concept of"local search efficiency",defined as the ratio of the number of receiving individuals to the number of searching individuals,is introduced and used to balance the allocation of computing resources between global search and local search.By adjusting the search period and search probability of the local search at different stages through local search efficiency,the diversity and practical effectiveness of the Pareto solution can be significantly improved.We referenced the existing five effectiveness comparison indicators,and designed numerical experiments for different combinational disruption events,to test the effectiveness of the proposed initial population construction strategy and improved memetic algorithm.To facilitate a more effective comparison,this paper improved the memetic and NSGA-II algorithms,and combined them with the random initial population and initial population construction strategies to obtain four hybrid conditions:“memetic algorithm+initial population construction","NSGA-II algorithm+initial population construction","memetic algorithm+random initial population","NSGA-II algorithm+random initial population".Through numerical experiments,we found that,given the same initial population,the improved memetic algorithm proposed in this paper provided a better Pareto frontier;and,given the same algorithm,the initial population construction strategy proposed in this paper significantly improved the performance of the algorithm,thus demonstrating its advantages.This study further improves and theoretically enriches the body of research on combinational disruption management in a permutation flow shop environment where setup time and sequence are relevant factors,and in practice,can help facilitate effective production and the implementation of rescheduling programs to guide production practices,at times when enterprises may face combinational disruption events.