反相容工件系统的加权完工时间和的重新排序问题(英文)  

Rescheduling to Minimize Total Weighted Completion Time under Anticompatible Job Systems

作　　者：慕运动[1,2] 谷存昌[1,2] 周伟[1] 程瑶[1] 

机构地区：[1]河南工业大学理学院,郑州450001 [2]郑州大学数学系,郑州450052

出　　处：《工程数学学报》2010年第1期152-160,共9页Chinese Journal of Engineering Mathematics

基　　金：NSFC(10671183);NSFHN(082300410190);NSF of the Education Department of Henan Province (2008A110004);the Science Foundation (07XJC002);Doctor Science Foundation of Henan University of Technology

摘　　要：重新排序问题是指在原始工件已经安排好的情形下,新到的工件集与原始工件集一起重新再排序,这是实际工作中常见一类优化问题。本文考虑了单机上当工件加工时间与权重反相容时,在最大错位量约束下的加权完工时间和最小化的重新排序问题。对于提出的四个问题,即在最大序列错位、最大时间错位、总序列错位和总时间错位约束下的加权完工时间和重新排序,基于问题的结构性质,运用动态规划方法分别给出了这些问题的多项式时间或拟多项式时间算法。For the rescheduling problem on a single machine, a set of original jobs has already been scheduled to minimize some cost, then a new set of jobs arrive and create a disruption. The rescheduling problem in this paper is to minimize total weighted completion time under a limit of the maximum disruption when pj and wj of the jobs are anticompatible. In this paper, we consider the above rescheduling problem for jobs on a single machine. For the rescheduling problems under a limit of the maximum sequence disruption, or the maximum time disruption, or the total sequence disruption and the total time disruption, depending on their structure properties, we apply the dynamic programming method and give a polynomial time or pseudopolynomial time algorithm, respectively.

关 键 词：重新排序 单机 完工时间 错位量 反相容 

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