1绍撞、問題描述：
n個作業(yè){1正勒，2，…傻铣，n}要在由2臺機(jī)器M1和M2組成的流水線上完成加工章贞。每個作業(yè)加工的順序都是先在M1上加工，然后在M2上加工非洲。M1和M2加工作業(yè)i所需的時間分別為ai和bi鸭限。流水作業(yè)調(diào)度問題要求確定這n個作業(yè)的最優(yōu)加工順序，使得從第一個作業(yè)在機(jī)器M1上開始加工两踏，到最后一個作業(yè)在機(jī)器M2上加工完成所需的時間最少败京。
2、問題分析
直觀上梦染，一個最優(yōu)調(diào)度應(yīng)使機(jī)器M1沒有空閑時間赡麦，且機(jī)器M2的空閑時間最少。在一般情況下帕识，機(jī)器M2上會有機(jī)器空閑和作業(yè)積壓2種情況泛粹。設(shè)全部作業(yè)的集合為N={1，2渡冻，…戚扳，n}。S是N的作業(yè)子集族吻。在一般情況下帽借，機(jī)器M1開始加工S中作業(yè)時，機(jī)器M2還在加工其他作業(yè)超歌，要等時間t后才可利用砍艾。
將這種情況下完成S中作業(yè)所需的最短時間記為T(S,t)。流水作業(yè)調(diào)度問題的最優(yōu)值為T(N,0)巍举。
設(shè)π是所給n個流水作業(yè)的一個最優(yōu)調(diào)度脆荷，它所需的加工時間為 aπ(1)+T’。其中T’是在機(jī)器M2的等待時間為bπ(1)時懊悯，安排作業(yè)π(2)蜓谋，…，π(n)所需的時間炭分。記S=N-{π(1)}桃焕，則有T’=T(S,bπ(1))。
