加工能力受限的单机干扰管理研究

针对单机环境下最小化加权折扣加工时间和的排序问题,研究如何应对可预见的干扰事件。由于干扰事件使得机器加工能力受限,初始最优加工时间表不再可行,采用外包的方式来进行干扰管理。构建了排序模型,同时考虑原目标和与初始计划偏离的扰动目标,选择外包工件集并对所有工件进行重排序。为了求解得到的双目标排序问题,基于理想点法设计了一种动态规划算法和量子遗传算法相结合的算法。最后通过一个数值算例说明,该排序模型对于求解加工能力受限的单机干扰管理问题是有效的。

Disruption Management for Single Machine Scheduling with Processing Availability Constraints

The normal operations of service systems could easily be disrupted because of increased uncertainty in the environment.Disruption management aims to deal with the impact of disruptions timely and effectively,and recover the system with deviation cost as low as possible.Although disruption management was initially formulated and implemented in airline operations,it has now been widely applied in logistics distribution,operations management and machine scheduling.The machine is not always available in planning horizon because machine scheduling is subject to accidents,such as breakdown of raw material supply,machine maintenance and sudden arrival of jobs with higher priority.Since the initial optimal schedule is not always optimal or feasible,how to deal with disruptions and make adjustments to the initial schedule has become a hot topic. There have been some studies assuming that the disrupted machine is recoverable.However in practice the disruption in one processing center may last so long that it could not recover during planning horizon.Under such circumstance,outsourcing is adopted to handle the insufficient processing capacities.There exist two objectives concerning the decision makers in the processing center.The first one is the original objective measured by the weighted discounted completion times of all jobs,and the second one is the deviation cost objective measured deviations in completions times of all jobs.When information about the disruption is known,the decision maker needs to ascertain that job will be outsourced and transported to another processing center,and the transportation time could not be omitted. By analyzing the characteristics of the optimal solution in Theorem 1,we find that the bi-criteria scheduling problem could be converted to a set partitioning problem.Therefore,the ideal point method is adopted for the bi-criteria optimization problem.By solving two single objective problems using dynamic programming,the ideal point is obtained.In addition,the solution closest to ideal point in 2-dimentional objective space is chosen as a solution to the bi-criteria problem.Theorem 2 also proves that the solution obtained through ideal point method is a Pareto solution. When searching the solution closest to ideal point,the nonlinearity of the traditional optimization methods could not be directly used.Instead,a heuristic entitled Quantum-inspired Genetic Algorithm(QGA) is designed.In QGA,Qubit is adopted to encode the feasible solutions into individuals.Each individual in the population is evaluated by distance to the ideal point.The population evolves by updating the individual through quantum rotation gate operator.During evolution the generated infeasible solutions are repaired by certain strategies.When the generation number reaches a pre-assumed value,the algorithm terminates and the best solution in all generations is outputted as the optimal solution. In order to verify the effectiveness of the algorithm,a numerical experiment is carried out.By comparing the solutions obtained through dynamic programming,it is found out that the ideal point could not be reached.Figure 2 shows that the average and best distance to ideal point in the population decline during evolution and converge finally.Figure 3 shows that apart from the solution closet to ideal point,QGA could also obtain other Pareto solutions.Furthermore,the formulated heuristic based on ideal point method is compared with two other methods: rescheduling where only the original objective is considered and outsourcing the directly affected jobs.The findings show that the formulated heuristic in this paper could effectively lower the impact of disruptions and keep the original objective at an acceptable level.To summarize,the formulated method could serve as an effective decision-making tool for outsourcing in the face of machine disruption problems.