【摘要】：流水調度問題(flow shop)是近幾十年來調度算法研究的重點問題模型,也是車間生產過程中涉及較多的一類模型。流水調度問題可定義為：有m臺處理機,來處理n個作業(yè),每個作業(yè)在每臺處理機上都有一定的處理時間,所有作業(yè)都有相同的加工順序,每臺處理機只處理一道工序,且每臺處理機一次只能處理一個作業(yè),該問題的目標就是得到一個可行調度方法,使得完成所有作業(yè)所用的時間最短。 之前很多文獻對該問題進行了研究,但多數研究都是假設的理想狀態(tài)下的問題模型,不是忽略兩臺處理機之間的運輸時間,就是認為負責運輸的運輸機的容量是無限的。而本文則明確考慮了運輸機的運輸時間和容量,從而進行對該模型的計算復雜性的分析和研究。 本文研究的是有兩臺處理機和一臺運輸機的流水線調度問題。在這個問題中,兩臺處理機A和B處理n個作業(yè),這些作業(yè)串行的在每臺處理機上處理,其在每臺處理機上的處理時間是確定的,且所有作業(yè)必須先在處理機A上處理,然后再運輸到處理機B上處理,有一臺運輸機負責將作業(yè)從處理機A運輸到處理機B,運輸時間是不依賴于作業(yè)的,每臺處理機有無限個緩存區(qū)來存放待處理的和處理完成的作業(yè)。本文主要討論了當運輸機的容量為1、容量為2、容量大于或者等于3的三種問題模型的計算復雜性。運輸機容量為1和容量大于或者等于3的情況,已在前人的研究成果中被證明出是強NP-hard問題,本文通過改變運輸時間條件重新構造實例,用更詳細的分析過程證明出這兩個模型是強NP-hard問題,同時說明了兩種證明方法的等價性。運輸機容量為2的問題模型在以往的文獻中一直是一個開放問題,沒有文章進行專門的研究,但本人已經在去年的一篇擬發(fā)表的文章中證明出來該問題是一個強NP-hard問題,本文重點說明了該證明方法和容量為1的模型的證明方法的等價性。 最后,本文還研究了運輸時間依賴于作業(yè)的處理時間的有兩臺處理機的流水調度問題模型,主要分析了每個作業(yè)的運輸時間是其在第一臺處理機上的處理時間的2倍的情況,我們證明出了該問題是可解的,并且給出了一個對約翰遜規(guī)則進行了擴展的算法來解決該問題。
[Abstract]:The pipelining scheduling problem (flow shop) is the key problem model of scheduling algorithm research in recent decades, and it is also a kind of model involved in the workshop production process. Pipelining scheduling problem can be defined as: there are m processors to handle n jobs, each job has a certain processing time on each processor, all jobs have the same processing sequence, each processor only handles one process. And each processor can only deal with one job at a time. The goal of this problem is to obtain a feasible scheduling method to minimize the time it takes to complete all jobs. Many previous literatures have studied the problem, but most of the studies are hypothesized ideal model of the problem, either neglecting the transport time between two processors or considering that the capacity of the transport aircraft responsible for transport is infinite. In this paper, the transport time and capacity of the transporter are explicitly considered, and the computational complexity of the model is analyzed and studied. In this paper, the pipeline scheduling problem with two processors and one transporter is studied. In this problem, two processors A and B process n jobs, which are processed serially on each processor, and their processing time on each processor is determined, and all jobs must first be processed on processor A. Then it was transported to processor B for processing, and a transporter was responsible for transporting the operation from processor A to processor B. the transport time was independent of the operation. Each processor has unlimited cache areas to store pending and processed jobs. In this paper, the computational complexity of three problem models with capacity of 1, capacity of 2 and capacity of more than or equal to 3 is discussed. When the capacity of the transporter is 1 and the capacity is greater than or equal to 3, it has been proved to be a strong NP-hard problem in the previous research results. This paper reconstructs an example by changing the transportation time condition. The two models are proved to be strong NP-hard problems by a more detailed analysis process, and the equivalence of the two methods is also illustrated. The problem model with transport plane capacity of 2 has been an open problem in the past literature, and there is no special research on it, but I have already proved that this problem is a strong NP-hard problem in a paper to be published last year. This paper focuses on the equivalence of the proof method and the proof method of the model with capacity 1. Finally, the pipelining scheduling model with two processors is studied, in which the transport time depends on the processing time of the operation, and the transport time of each job is analyzed to be twice the processing time of each job on the first processor. We prove that the problem is solvable and give an algorithm to extend Johnson's rule to solve the problem.
【學位授予單位】：大連理工大學
【學位級別】：碩士
【學位授予年份】：2014
【分類號】：TB497

【共引文獻】

相關期刊論文 前3條

1 顏潔;聶瑞華;;作業(yè)可分割的數據采集系統(tǒng)[J];華南師范大學學報(自然科學版);2014年05期

2 李愛冉;樊瑜瑾;韓騰;李浙昆;趙培林;王俊杰;;單舵輪AGV小車直線制動橫向穩(wěn)定性分析及優(yōu)化[J];機電一體化;2014年10期

3 李軍濤,Hiroshi Kise,Longyun Piao;基于最優(yōu)載具排序的交換循環(huán)型載具排序系統(tǒng)[J];蘇州大學學報(工科版);2004年05期

相關博士學位論文 前6條

1 宮華;鋼鐵企業(yè)一類考慮惡化和運輸的新型生產調度問題的理論研究[D];東北大學;2009年

2 蘇生;多工廠生產計劃與調度優(yōu)化模型與求解算法[D];哈爾濱工業(yè)大學;2007年

3 王鋒輝;面向區(qū)域智能運輸的多智能車輛協(xié)作研究[D];上海交通大學;2009年

4 任小龍;基于Petri網的FMS調度問題研究[D];西安電子科技大學;2010年

5 關靜;流程工業(yè)生產與運輸協(xié)調物流調度理論研究[D];東北大學;2008年

6 汪磊揚;一類帶批運輸的排序問題研究[D];華東理工大學;2012年

相關碩士學位論文 前10條

1 向桂英;單機供應鏈排序集成性研究[D];華東理工大學;2012年

2 傅青;流水作業(yè)成套訂單數及其多目標排序研究[D];華中科技大學;2007年

3 鄭瓊沂;工件有體積的平行機加工及分批運輸[D];曲阜師范大學;2013年

4 凌忠奇;AGV小車路徑規(guī)劃算法的探究[D];機械科學研究總院;2013年

5 聶嘉明（Nip Kameng）;若干車間排序問題和最短路問題的組合問題[D];清華大學;2013年

6 高曉明;具有存儲約束的單機加工兩級制造鏈協(xié)同調度問題研究[D];東北大學;2011年

7 張卿匯;兩類平行機排序問題的算法設計與分析[D];浙江理工大學;2014年

8 韓騰;AGV驅動與制動性能分析研究[D];昆明理工大學;2014年

9 秦高陽;航空緊固件企業(yè)成組調度研究[D];重慶大學;2014年

10 易哲;煙草車間排程規(guī)劃算法設計[D];中南大學;2013年

，

本文編號：2469346