加权折扣单机排序干扰管理模型和算法研究

为解决机器排序中由于干扰事件的发生使初始最优加工时间表无法按计划执行的问题,构建同时考虑原目标和扰动目标的双目标干扰管理模型,对初始最优加工时间表进行调整并对未完工工件进行重排序;在双目标干扰管理模型中,原目标由所有工件的加权折扣完工时间和来度量,扰动目标由重排序后工件完工时间的变化来度量;结合量子比特在表示解的多样性方面的优点和非支配排序遗传算法在处理多目标排序问题上的优点,设计一种量子遗传算法和非支配排序遗传算法相结合的启发式进化算法对构建的模型进行求解。在数值算例中,通过比较若干项针对有效解集的性能指标发现,该混合算法求得的有效解集在多样性和与最优有效前沿的邻近性等方面优于目前得到广泛应用的非支配排序遗传算法,验证了构建的模型和算法对于求解机器排序干扰管理问题的有效性。

Disruption Management Model and Algorithm for Problem of Weighted Discounted Single Machine Scheduling

In machine scheduling,the original optimal schedule usually couldn′t be executed as planned due to all sorts of disruption.In order to adjust the original optimal schedule and reschedule the unfinished jobs,this research formulates the bi-criteria model which considers both the original objective and the deviation objective.The original objective is measured by the weighted discounted sum of processing times,while the deviation objective is measured by the change of jobs′ completion times.A hybrid heuristic algorithm is designed to solve the problem.It combines the advantages of Qubit representation in solution diversity and the advantages of Non-dominated Sorting Genetic Algorithm(NSGA-II) in dealing with multiple objective scheduling.By comparing several performance metrics for Pareto solution set in numerical simulation,it is concluded that the hybrid algorithm is superior to the widely-used NSGA-II in both solution diversity and proximity to optimal Pareto front.So the hybrid heuristic algorithm is proved to serve as an effective tool for the machine disruption management problem.