论文摘要
本文主要研究的是具有非交叉维修时间的平行机在线排序问题。在排序问题中，平行机排序是其中最活跃的分支之一。无论是对离线的还是在线的，数十年来人们进行了大量的研究。关于平行机排序问题的文献大都是假设所有机器自始至终都是可使用的，然而这种假设在实践中可能不现实。在生产过程中，由于对机器的预防性维修或机器突然出现故障都会导致机器在某一段时间内不能使用，有时候我们也把机器不能使用的这一段时间叫做这台机器的禁用区间，所以我们有必要把这些因素考虑到排序问题中去，再做出合理的决策非交叉维修时间指的是对于m台平行机（Parallel identical machines）的集合M={[Mi|i=1，2，…m}来说，每一台机器Mi上有一个维修时间段[ai，bi)，且0≤ai＜bi，i=1，2，…m，并且这m个维修时间段满足或者完全重合或者完全分离，也就是说；或者满足ai=a，bi=b，a，b是常数，i=1，2，…m；或者满足ai+1≥bi，i=1，2，…m-1．在本文的讨论中，对于前者我们还假定b-a≤Pmax，对于后者我们假定ai+1-bi≥Pmax，i=1，2，…m-1，其中Pmax是工件集中工件的最大加工时间。前者所述我们用D1={[ai，bi)|0≤ai＜bi，ai=a，bi=b，b-a≤Pmax，i=1，2，…m}来表示，后者所述用D2={[ai，bi)|0≤ai＜bi，ai+1-bi≥Pmax，i=1，2，…m-1)来表示。所谓在线指的是工件集是按照某个顺序到达的，是什么顺序我们事先不知道，工件的所有性质在它到来之前是未知的，工件在到来之前不能被安排加工。只有当工件Jj-1。已经被安排好之后工件Jj才到达，否则，工件Jj不出现，并且工件Jj一出现就要立即被安排到某台机器上加工，一旦被安排就不能再改变。在这种类型的排序问题中，又可分为两种情形来考虑：一种是中断后可继续加工的情形，比如说在某个时刻某台机器上有某个工件正在加工还没有完工，而这台机器在这个时刻需要进行维修，那么在这一时刻可以中断正在加工的这个工件，等到这台机器维修完之后，再接着加工被中断的工件剩余的部分。一种是中断后不可继续加工的情形，也就是说；对于上面的情形而言，被中断的工件在机器维修完之后必须被重新开始加工，相当于前面被加工的部分作废．这两种情形在排序模型中我们分别用符号r-a（Resumable availability）和nr-a（Nonresumable availability）来表示，这是借文献[1]的用法。在上述情况下，我们的任务是找一个把所有工件安排到机器集上之后使得我们所要的某个目标函数值达到尽可能优的方案，用排序论的语言来说也就是找一个尽可能好的算法。在这篇文章里，我们主要对m=2和3的情形进行了讨论，我们研究的问题的模型用三参数可表示为P2|on-line-list；r-a；D1|CmaxP2|on-line-list；nr-a；D1|CmaxP2|on-line-list；nr-a；D2|CmaxP3|on-line-list；nr-a；D1|Cmax本文的主要结果是对问题P2|on-line-list；r-a；D1|Cmax，找到了一个竞争比是2的最好的算法并给出了证明。对问题P2|on-line-list；nr-a；D1|Cmax，我们将证明此排序问题的任意在线算法的下界不小于2.79，并给出一个竞争比不大于2.8的在线算法。对问题P2|on-line-list；nr-a；D2|Cmax，我们将证明此排序问题的任意在线算法的下界不小于1.99，并证明了LS算法的竞争比不大于2．对于m=3的情形，即对问题P3|on-line-list；nr-a；D1|Cmax，我们将证明此排序问题的任意在线算法的下界不小于3-ε，并给了一个竞争比不大于10／3的在线算法。