带精确时间延迟的单机排序问题

Single machine scheduling problem with exact delays

主要研究带精确时间延迟的单机排序问题。每个工件Jj(j=1,2,…,n)有两道工序aj、bj,第一道工序先于第二道工序加工,第一道工序的完工时间caj与第二道工序的开始时间sbj之间存在一个精确时间延迟exact lj,即sbj=caj+lj。所有工序操作时间都相等aj=bj=a(j=1,2,…,n),且精确时间延迟是工序操作时间的整数倍lj=ka(k∈N+)。所有工序在一台机器上执行,分别以极小化加权总完工时间,最大延误和总延误数为目标函数,设计了最优算法。

The single machine scheduling problem with exact delays is studied.Each workpiece Jj(j=1,2,…,n)has two processes aj、bj.The first process caj is processed before the second process sbj.There is an exact time delay exact lj between the completion time of the first process and the start time of the second process,that is to say sbj=caj+lj.All operation times are equal aj=bj=a(j=1,2,…,n),and the exact time delay is an integral multiple of operation time lj=ka(k∈N+).All processes are performed on one machine.The optimal algorithm is designed by the objective function of minimizing the total weighted completion time,the maximum delay and making the total delay minimum number.