带有多次速率改变行为的单机排序问题  

Single machine scheduling problem with rate-modifying activities.

作　　者：张安[1] 何勇[1] 

机构地区：[1]浙江大学数学系,浙江杭州310027

出　　处：《浙江大学学报（理学版）》2006年第3期272-275,281,共5页Journal of Zhejiang University（Science Edition）

基　　金：国家自然科学资金资助项目(10271110)

摘　　要：研究机器带有多次速率改变行为的单机排序问题.机器可以通过不超过t个时段的中断来调整加工速度,即每个工件在每次中断时段前后加工的加工时间可能不同.因此问题就需要决定是否中断,以及何时中断,使得最大完工时间、完工时间总和、加权完工时间总和等尽可能小.对任意固定的t,关于最大完工时间和完工时间总和目标分别给出了多项式时间最优算法,对满足正则假设的加权完工时间总和目标也给出了一个多项式时间最优算法.A single machine scheduling problem with rate-modifying activities is studied. The machine is supposed to have at most t breakdown time windows so as to modify its velocity, that is, the process time of each job may be different between before and after the breakdown. Thus the problem is to make a decision on whether and when to start the breakdown so as to minimize the maximum completion time, the total completion time or the weighted total completion time. For any fixed t, polynomial time optimal algorithms for the first two objectives are given respectively; and for the third objective a polynomial time optimal algorithm is also provided under the regularity assumption.

关 键 词：单机排序 速率改变行为 最优算法 计算复杂性 

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