帶運(yùn)輸機(jī)的流水調(diào)度的復(fù)雜性研究.pdf

1、流水調(diào)度問題(flowshop)是近幾十年來調(diào)度算法研究的重點(diǎn)問題模型，也是車間生產(chǎn)過程中涉及較多的一類模型。流水調(diào)度問題可定義為:有m臺(tái)處理機(jī)，來處理n個(gè)作業(yè)，每個(gè)作業(yè)在每臺(tái)處理機(jī)上都有一定的處理時(shí)間，所有作業(yè)都有相同的加工順序，每臺(tái)處理機(jī)只處理一道工序，且每臺(tái)處理機(jī)一次只能處理一個(gè)作業(yè)，該問題的目標(biāo)就是得到一個(gè)可行調(diào)度方法，使得完成所有作業(yè)所用的時(shí)間最短。
　　之前很多文獻(xiàn)對(duì)該問題進(jìn)行了研究，但多數(shù)研究都是假設(shè)的理想狀態(tài)下的問

2、題模型，不是忽略兩臺(tái)處理機(jī)之間的運(yùn)輸時(shí)間，就是認(rèn)為負(fù)責(zé)運(yùn)輸?shù)倪\(yùn)輸機(jī)的容量是無限的。而本文則明確考慮了運(yùn)輸機(jī)的運(yùn)輸時(shí)間和容量，從而進(jìn)行對(duì)該模型的計(jì)算復(fù)雜性的分析和研究。
　　本文研究的是有兩臺(tái)處理機(jī)和一臺(tái)運(yùn)輸機(jī)的流水線調(diào)度問題。在這個(gè)問題中，兩臺(tái)處理機(jī)A和B處理n個(gè)作業(yè)，這些作業(yè)串行的在每臺(tái)處理機(jī)上處理，其在每臺(tái)處理機(jī)上的處理時(shí)間是確定的，且所有作業(yè)必須先在處理機(jī)A上處理，然后再運(yùn)輸?shù)教幚頇C(jī)B上處理，有一臺(tái)運(yùn)輸機(jī)負(fù)責(zé)將作業(yè)從處理機(jī)A

3、運(yùn)輸?shù)教幚頇C(jī)B，運(yùn)輸時(shí)間是不依賴于作業(yè)的，每臺(tái)處理機(jī)有無限個(gè)緩存區(qū)來存放待處理的和處理完成的作業(yè)。本文主要討論了當(dāng)運(yùn)輸機(jī)的容量為1、容量為2、容量大于或者等于3的三種問題模型的計(jì)算復(fù)雜性。運(yùn)輸機(jī)容量為1和容量大于或者等于3的情況，已在前人的研究成果中被證明出是強(qiáng)NP-hard問題，本文通過改變運(yùn)輸時(shí)間條件重新構(gòu)造實(shí)例，用更詳細(xì)的分析過程證明出這兩個(gè)模型是強(qiáng)NP-hard問題，同時(shí)說明了兩種證明方法的等價(jià)性。運(yùn)輸機(jī)容量為2的問題模型在以往