發(fā)布時間：2018-02-03 07:06

  本文關鍵詞： 兩階段 自由車間 流水車間 近似算法 最壞情況界　出處：《浙江理工大學》2016年碩士論文　論文類型：學位論文

【摘要】：本文主要研究了兩階段車間作業(yè)排序問題:第一類是兩階段自由作業(yè)排序問題,第二類是兩階段混合車間作業(yè)排序問題。研究的重點是,證明這些問題的計算復雜性,設計問題的近似算法,并對算法的最壞情況界進行證明。全文共分為四章。具體如下:第一章簡要的介紹排序的基本理論。第二章主要研究一類新型兩階段自由作業(yè)排序問題。第一階段是自由車間,第二階段是流水車間,目標是極小化最大完工時間。其中要求工件一旦進入流水車間的兩臺機上加工,必須完成流水車間加工才可進行下一階段任務。本章分兩種情形,目標均是極小化最大完工時間。情形一:考慮一般的情況,第一階段機器為m臺,第二階段機器為兩臺,本章提出一個近似算法,并證明其最壞情況界為2;情形二:第一階段機器為一臺,第二階段機器為兩臺,本文對問題進行復雜性證明,證明該問題是NP難問題,并給出一個5/3-近似算法及其最壞情況界證明。第三章主要研究一類兩階段混合車間作業(yè)排序問題。第一階段是自由車間共兩臺機,第二階段是流水車間共兩臺機。其中工件可選擇任一階段的車間進行加工,目標是極小化最大完工時間。本文對問題的復雜性進行證明,證明該問題是一般NP難問題,同時提出一個近似算法,并證明其最壞情況界為27/14。第四章總結全文并提出相關問題進一步的研究方向。
[Abstract]:In this paper, we mainly study the two-stage job-shop scheduling problem: the first is the two-stage free job scheduling problem, the second is the two-stage hybrid workshop scheduling problem. Prove the computational complexity of these problems, design the approximate algorithm of the problem. And prove the worst-case bound of the algorithm. The full text is divided into four chapters. The details are as follows:. The first chapter briefly introduces the basic theory of sorting. The second chapter mainly studies a new type of two-stage free job scheduling problem. The first stage is the free workshop. The second stage is the income workshop, with the goal of minimizing the maximum completion time, which requires the workpiece to be processed on two machines once it enters the income workshop. Income workshop must be completed before the next phase of the task. This chapter is divided into two cases, the goal is to minimize the maximum completion time. Case 1: considering the general situation, the first stage of the machine is m. There are two machines in the second stage. In this chapter, an approximate algorithm is proposed and its worst-case bound is proved to be 2. Case two: one machine in the first stage and two machines in the second stage. In this paper, we prove the complexity of the problem and prove that the problem is NP-hard. A 5 / 3-approximation algorithm and its worst-case bound proof are given. In Chapter 3, we mainly study a class of two-stage hybrid shop scheduling problem. The first stage is a two-machine free workshop. In the second stage, there are two machines in income workshop, in which the workpiece can be processed in any stage, and the goal is to minimize the maximum completion time. The complexity of the problem is proved in this paper. It is proved that this problem is a general NP-hard problem, and an approximate algorithm is proposed, and the worst-case bound is proved to be 27 / 14. 4th. The full text is summarized and the further research directions of related problems are proposed.
【學位授予單位】：浙江理工大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：O223

【相似文獻】

相關期刊論文 前10條

1 姜振多;孫世杰;吳志剛;;排序問題的穩(wěn)定性分析(英文)[J];Journal of Shanghai University(English Edition);2008年01期

2 譚素平;;排序問題的分類與特點[J];科技信息;2012年36期

3 越民義,韓繼業(yè);排序問題中的一些數(shù)學問題[J];數(shù)學的實踐與認識;1976年03期

4 越民義,韓繼業(yè);同順序m×n排序問題的一個新方法[J];科學通報;1979年18期

5 吳家強;用分段選優(yōu)法求解“排序問題”[J];武漢水利電力學院學報;1979年03期

6 戴志勇;;一類排序問題最優(yōu)工序定義的等價性[J];武漢鋼鐵學院學報;1979年02期

7 韓繼業(yè);排序問題的一個判別條件和一類特殊的m×n排序問題[J];應用數(shù)學學報;1980年04期

8 吳在德;梁學信;;排序問題計算加工時間的一種方法及其一個應用[J];華僑大學學報;1981年01期

9 葉懋冬;;關于過竿問題與多臺機床上零件加工的排序問題(Ⅰ)[J];浙江大學學報;1982年04期

10 徐本順;有提前和延誤損失的一類排序問題[J];華中工學院學報;1983年04期

相關會議論文 前10條

1 柏孟卓;唐國春;;加工時間可控的同時加工排序問題[A];2006年中國運籌學會數(shù)學規(guī)劃分會代表會議暨第六屆學術會議論文集[C];2006年

2 張蓮珠;;關于六角鏈的極值和排序問題的一些結果[A];中國運籌學會第六屆學術交流會論文集（上卷）[C];2000年

3 周支立;李懷祖;;有重疊區(qū)域的兩抓鉤周期性排序問題的求解[A];Systems Engineering, Systems Science and Complexity Research--Proceeding of 11th Annual Conference of Systems Engineering Society of China[C];2000年

4 孫世杰;陳躍;;參數(shù)可控的排序問題[A];2001年全國數(shù)學規(guī)劃及運籌研討會論文集[C];2001年

5 張玉忠;;分批排序問題研究[A];中國運籌學會第七屆學術交流會論文集（上卷）[C];2004年

6 張玉忠;;分批排序問題研究[A];中國運籌學會第七屆學術交流會論文集（中卷）[C];2004年

7 譚萬達;;二元對比排序中的最少逆序原理[A];中國系統(tǒng)工程學會模糊數(shù)學與模糊系統(tǒng)委員會第五屆年會論文選集[C];1990年

8 呂緒華;楊漢興;;求解裝配式排序問題的歸并算法及其性能比研究[A];中國運籌學會第六屆學術交流會論文集（下卷）[C];2000年

9 樊保強;;帶倉儲約束的準時排序問題[A];中國運籌學會第九屆學術交流會論文集[C];2008年

10 陳榮軍;唐國春;;自由作業(yè)環(huán)境下的供應鏈排序問題[A];中國運籌學會第九屆學術交流會論文集[C];2008年

相關博士學位論文 前10條

1 高強;一些現(xiàn)代排序問題的算法設計與分析[D];華東理工大學;2015年

2 谷存昌;工件的加工和配送協(xié)作排序問題[D];曲阜師范大學;2015年

3 仲維亞;供應鏈管理中的若干排序問題研究[D];浙江大學;2008年

4 尹曉;基因組重組排序問題的算法研究[D];山東大學;2010年

5 余煒;若干網(wǎng)絡排序問題的算法和復雜性研究[D];華東理工大學;2010年

6 張安;帶服務等級的在線排序問題及相關問題研究[D];浙江大學;2009年

7 鄭睿;鋼鐵生產中的批處理機作業(yè)排序問題算法研究[D];復旦大學;2009年

8 季敏;當代工業(yè)中的若干排序問題研究[D];浙江大學;2006年

9 李好好;若干排序問題研究[D];浙江大學;2014年

10 丁國生;多代理競爭排序問題的研究[D];上海大學;2009年

相關碩士學位論文 前10條

1 李韋萱;兩類帶有維修的排序問題[D];沈陽師范大學;2015年

2 周雨波;與工件釋放時間和交貨時間有關的排序問題及近似算法[D];蘭州大學;2015年

3 張龍;優(yōu)化交貨期窗口的單機供應鏈排序問題[D];曲阜師范大學;2015年

4 于萌萌;工件帶有惡化效應的博弈排序問題[D];曲阜師范大學;2015年

5 李雨潔;恒速機下的有限資源博弈排序最優(yōu)性研究[D];曲阜師范大學;2015年

6 尚明明;帶有GDD假設的幾類重新排序問題研究[D];鄭州大學;2015年

7 黃保斌;分批的供應、加工、配送供應鏈排序問題[D];曲阜師范大學;2015年

8 蘇曉彤;機器具有維護時段的帶運輸排序問題研究[D];浙江理工大學;2016年

9 楊佳雯;兩階段車間作業(yè)排序問題的研究[D];浙江理工大學;2016年

10 胡愛麗;幾個不同參數(shù)可控的排序問題的討論[D];蘇州大學;2009年

，

本文編號：1486763