处理机具有不同开始加工时间的可中断排序问题

本文对处理机具有的不同开始加工时间的可中断排序问题进行讨论，得到下面结论：若处理机具有相同开始加工时间的可中断排序问题存在最优排序算法，则相应的处理机具有不同开始加工时间的可中断排序问题也存在最优排序算法。

可中断半在线排序问题

讨论两台同型机上的可中断半在线排序问题,目标函数为极大化最小的机器完工时间Cmin.首先考虑已知所有工件的加工时间在p和rp(p>0,r≥1)之间的情形,对任意的参数r,设计了最优半在线算法.接着,对已知最大工件加工时间的情形作了研究,得到了一个竞争比为54的最优半在线算法.

具有优先约束的不完全恒速机排序问题

讨论了任务具有优先约束的可中断不完全恒速机排序问题，若处理机具有不同开始加工时间的可中断排序问题存在最优算法，则相应的不完全恒速机排序问题也有最优算法。

问题1｜pmtn,d_j｜h_(max)的一个最优算法

给出并证明了求解问题１｜ｐｍｔｎ，ｄｊ｜ｈｍａｘ的一个最优算法。

问题1｜pmtn,d_j｜h_(max)的一个最优算法

研究了具有工期限制、可以中断加工的排序问题１｜ｐｍｔｎ，ｄｊ｜ｈｍａｘ，给出了使最大费用函数ｈｍａｘ＝ｍａｘ｛ｈ１（ｓ１），…。

已知总和的可中断半在线排序算法

文章研究了平行机上的一个半在线排序问题.假定预先已知所有工件的加工时间总和,工件的加工可中断,目标是极大化最小的机器完工时间和极小化最大的机器完工时间.针对这两种目标情形,分别给出了竞争比为1的半在线算法,从而是最优的.