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

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

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

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