证1 若J是可行解,则必存在调度序列δ r1r·r1 使得 d;≥j,1≤j≤k 现设按题目要求调整序列δ’。 在8’的调度序列中任取1个作业r;(1≤i≤k) ●若i=dn,则r;的位置不变 ●若i<d1且dx1=j,则将r调整到j处,原r1+1,r+2,…,r向前移 位,可保持调整后的d-≥j(1≤j≤k) 每做一次调整后,调整的元素固定下来。若调整过程中,r;要调的 地方的作业r;已被固定,则继续往前寻找,直到找到没有被固定的作业 处 每次在δ’中选取1个没有固定下位置的作业做上述调整,k次后作 业顺序定下来,且能保持作业的执行时间不不违反作业期限,故J可行时, 用题中给出的方法可以解决作业排序。 存在的问题:调整后得到的调度序列可能不等于题目中给出的调度 序列。证1： 若J是可行解，则必存在调度序列δ’=r1r2…rk，使得 drj≥j,1≤j≤k 现设按题目要求调整序列δ’。 在δ’的调度序列中任取1个作业ri(1≤i≤k) ●若i=dri，则ri的位置不变 ●若i＜dri且dri=j，则将ri调整到j处，原ri+1,ri+2,…,rj向前移一 位，可保持调整后的drj≥j（1≤j≤k） 每做一次调整后，调整的元素固定下来。若调整过程中，ri要调的 地方的作业rj已被固定，则继续往前寻找，直到找到没有被固定的作业 处。 每次在δ’中选取1个没有固定下位置的作业做上述调整，k次后作 业顺序定下来，且能保持作业的执行时间不不违反作业期限，故J可行时， 用题中给出的方法可以解决作业排序。 存在的问题：调整后得到的调度序列可能不等于题目中给出的调度 序列