论文部分内容阅读
讨论两台平行机排序问题，有一台机器在某一个特定时刻可能产生中断，中断持续时间长短满足相应的概率，且工件转移到另一台机器上加工需要考虑运输时间．证明该问题是NP-困难的，设计一个复杂性为O（n^3（TP）^1）的动态规划算法，调整机器原有的工件排序，使得目标函数为带权重的总完工时间期望值最小．其中,n是工件的个数，TP是所有工件的加工时间之和，