最小化最大加权完工时间重新排序研究  

Rescheduling to Minimize the Maximum Weighted Completion Time

作　　者：臧西杰[1] 李士生[1] 王曦峰 

机构地区：[1]中原工学院理学院,郑州450007

出　　处：《系统科学与数学》2017年第11期2293-2300,共8页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金(11401605;11501279)资助课题

摘　　要：重新排序模型可以描述如下:一组原始工件已经按照某个准则做好最优加工(排序)方案,但是还没有开始加工.此时,另一组新工件突然到达,需要与原始工件一起加工.生产部门需要调整已有的加工方案,使得在原始工件不打乱太多的情形下得到一个合理的排序.本文研究最大加权完工时间的重新排序问题,问题的目标是:1)在原始排序错位限制的条件下最小化最大加权完工时间;2)最小化最大加权完工时间与原始排序的错位的加权和.在本文研究中我们假设所有工件在0时刻到达.文章的主要结果:对于Γ∈{D_(max)(π~*),△_(max)(π~*)},给出了问题1|Γ≤k|max w_jC_j和问题1‖maxw_jC_j+μΓ多项式时间的求解算法;证明了问题1|∑△_j(π~*)≤k|max w_jC_j和问题1‖max w_jC_j+μ∑△_j(π~*)是强NP-困难的.The model of rescheduling can be stated as follows jobs has been scheduled, unexpectedly before the but has not been processed. Then a new A set of original set of jobs arrives processing starts and has to be scheduled on a common machine with the set of original jobs. The production planners need to adjust the existing schedule and make a trade-off between the scheduling cost and the disruptions of the original jobs. In this paper, we study the rescheduling problem with the maximum weighted completion time of all jobs as the scheduling cost. The goal of the problem is to minimize either 1） the maximum weighted completion time of the jobs under an upper restriction on the disruption constraints of the original schedule, or 2） the weighted sum of the maximum weighted completion time of the jobs and the disruption cost of the original schedule. All jobs arrive at time zero. The main results of this paper are as follows： For F c {Dmax（π）, Amax（π）}, we provide polynomial time algorithms for problems lIF 〈 kl maxwC and iII maxwC ＋ μF; We alsoshow that problems 1//maxwJG＋p∑△J（π） are strongly NP-hard.

关 键 词：重新排序 错位 最大加权完工时间 NP-困难 

分 类 号：O223[理学—运筹学与控制论]