平行机上单位加工时间加权总完工时间排序问题的反问题
Inverse Problem of Total Weighted Completion Time Objective with Unit Processing Time on Identical Parallel Machines
-
摘要: 在给定工序下, 排序问题的反问题研究目标是对于预先给定的加工任务, 要求确定加工时间或者工件权重的最小调整值, 使得给定的工件排序最优。 本文研究了平行机上单位加工时间的加权总完工时间排序问题的反问题, 即对于给定的加工工序, 在不同范数下, 通过最小限度调整工件的权值, 实现给定加工工序最优, 同时满足调整权值后,目标函数值不超过原来的值。Abstract: In inverse scheduling problems, a job sequence is given and the objective is to determine the minimal perturbation to process times or weights of jobs so that the given schedule becomes optimal with respect to a preselected objective function. In this paper, we study the inverse problem of the total weighted completion time objective with unit processing time on identical parallel machines. The weights are minimally adjusted so that a given target job sequence becomes an optimal schedule for different norms under the constraints that the resulting objective value based on the adjusted weights is no more than the original objective value.