可能产生中断且考虑运输的两台平行机排序问题  

Two parallel machines scheduling under potential disruption with transportation considerations

作　　者：魏小兰[1] 沈灏[1] 叶赛英[2] 

机构地区：[1]杭州电子科技大学理学院,浙江杭州310018 [2]浙江科技学院理学院,浙江杭州310023

出　　处：《浙江大学学报（理学版）》2009年第2期144-146,152,共4页Journal of Zhejiang University（Science Edition）

基　　金：浙江省自然科学基金资助项目(Y606026)

摘　　要：讨论两台平行机排序问题.有一台机器在某一个特定时刻可能产生中断,中断持续时间长短满足相应的概率,且工件转移到另一台机器上加工需要考虑运输时间.证明该问题是NP-困难的,设计一个复杂性为O(n3(TP)4)的动态规划算法,调整机器原有的工件排序,使得目标函数为带权重的总完工时间期望值最小.其中,n是工件的个数,TP是所有工件的加工时间之和.Two parallel-machines scheduling problem is considered, in which there is a possibility that a disruption may happen to one of the two parallel machines at a particular time and last for a period of time with a certain probability. The NP-hardness of the problem is proved. A dynamic algorithm is provided, which adjusts the original scheduling and minimizes the expected total weighted completion times, and the complexity is O（n^3（TP）4 ）, where n is the number of jobs and TP is the total process time of all the jobs.

关 键 词：动态规划 平行机排序 中断 运输 

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