【摘要】 在安装时间和次序相关的单机调度问题中,为应对突发性的工件优先级变动造成的影响,构建了双目标重调度模型。原目标为生产的流程时间,扰动目标为工件的加工次序扰动。针对模型中的双目标,设计了基于有效解的两阶段混合启发式算法进行求解,在原目标和扰动目标之间进行权衡。混合算法第一阶段里,基于任意单个工件次序变化将双目标问题转化成单目标TSP问题,利用最近邻域和插入混合求得单目标问题的若干解,构成初始种群。第二阶段中基于非支配排序遗传算法在处理多目标问题上的优势,对初始种群进行扩展搜索,最后输出问题的有效前沿。通过数值试验运算比较分析若干针对有效解集的指标,验证了混合算法求得的解集在多样性和临近性上要优于单纯的非支配排序遗传算法。该混合算法可以有效地解决具有安装时间的加工次序扰动问题。更多还原

【Abstract】 In this paper,a disruption management problem on single machine scheduling with sequence dependent setup times 1|sij|Cmax is studied.It is originated from practical situations where jobs come from different job families,and during the implementation of initial schedule the priority of certain job would besuddenly upgraded,causing disruption to the original plan.This makes it necessary to consider jobs’ sequence deviation from original plan during rescheduling,which is calculated based on job i’s relative position to job j in the revised schedule.In this paper,a bi-objective rescheduling model is built,considering both Cmaxand sequence deviation.In order to effectively solve the model,local search is combined with global search and a two-stage approach is designed.In stage 1construction heuristic based on mixed Nearest Neighbor and Insertion is used to obtain good initial solutions for stage 2to make extension search along the Pareto front.Computational study shows that the proposed approach outperforms the widely applied NSGA-II in both proximity and diversity metrics.And for decision-makers,better decision alternatives could be provided for the trade-off between production cost and deviation of disruption.The research sets an example for applying hybrid metaheuristic to deal with disruption in machine scheduling and computational results could serve as comparison for further studies of this problem.更多还原