兩機無等待流水車間調(diào)度問題與仿真

一、題目

兩機無等待流水車間的調(diào)度與仿真

二、指導(dǎo)思想和目的要求

畢業(yè)設(shè)計（論文）是培養(yǎng)學(xué)生自學(xué)能力、綜合應(yīng)用能力、獨立工作能力的重要教學(xué)實踐環(huán)節(jié)。在畢業(yè)設(shè)計中，應(yīng)獨立承擔(dān)一部分比較完整的工程技術(shù)設(shè)計任務(wù)。要求學(xué)生發(fā)揮主觀能動性，積極性和創(chuàng)造性，在畢業(yè)設(shè)計中著重培養(yǎng)獨立工作能力和分析解決問題的能力，嚴(yán)謹(jǐn)踏實的工作作風(fēng)，理論聯(lián)系實際，以嚴(yán)謹(jǐn)認(rèn)真的科學(xué)態(tài)度，進(jìn)行有創(chuàng)造性的工作，認(rèn)真、按時完成任務(wù)。針對兩機無等待流水車間調(diào)度問題, 提出目標(biāo)函數(shù)最大完工時間最小化的快速算法, 并給出算法的復(fù)雜度.分析兩機無等待流水車間調(diào)度問題的排列排序性質(zhì),證明了兩機無等待流水車間調(diào)度問題的可行解只存在于排列排序中,排列排序的最優(yōu)解一定是兩機無等待流水車間調(diào)度問題的最優(yōu)解.最后研究了同時包含普通工件和無等待工件的兩機流水車間調(diào)度問題的復(fù)雜性,為進(jìn)一步研究兩機無等待流水車間調(diào)度問題提供了理論依據(jù)。

三、進(jìn)度和要求

第一階段：（共計5周）

第一周及第二周，翻譯并完成教師指定的英文文獻(xiàn)翻譯； 

第三周及第五周，對所研究課題有個全面的了解。

第二階段：（共計5周）

完成方案的提出，學(xué)習(xí)和用已知的方案方法進(jìn)行實際問題的解決方案的提出和仿真。

第三階段：（共計5周）

撰寫論文及評閱。

四、主要參考書及參考資料

[1] S.M.Johnson.optimal Two-and Three-Stage Production Scheduling with Set-up Time Included[J]. Naval Research Logistics Quarterly.1954, 1:61-68

[2] Story A.E, Wagner H.M.Computational Experience whit Integer Programming for Job-shop Schdeling.Industrial Scheduling,Chap.14,Prentice-Hall,1963

[3] Gavett J.W.Three Heuristic Rules for Sequencing Jobs to a Single Production Facility[J].   Mgmt.Sci.1965,11:B166-176

[4] S.Panwalker,Wafik Iskander.A Survey of Scheduling[J].Ops.Res.1977, 25(1):45-61

[5] Stephen,C.Graves.A Review of Production Scheduling[J].Ops.res.1981,29（4）:646-675

[6] M.S.Fox.ISIS:A Retrospective Intelligent Scheduling.Intelligent Scheduling,Kaufmann, ed:Michael B.Morgan,1994:3-28

[7] B.Giffler,GL.Thompson.Algorithms for Solving Production Scheduling Problems[J].Ops   Res.1960,8:487-503

[8] 董海，梁迪．設(shè)施規(guī)劃與物流分析．北京：機械工業(yè)出版社．2005

[9] Baker K R.A Comparative Study of Flow Shop Algonithms [J].Ops Res.1975(23）:62-73

[10] 王偉玲，馬正元，王玉生．生產(chǎn)調(diào)度問題研究的動態(tài)與趨勢[J]．管理技術(shù)，2005年第5期．

[11] 鄭璐，顧鑫生，不確定條件下的零等待Flow Shop生產(chǎn)調(diào)度問題[J]．華東理工大學(xué)學(xué)報2004，30（2）：188-194．

[12] S.Panwalker, Wafik Iskander.A Survey of Scheduling[J].Ops.Res.1977, 25（1）:45-61.

[13] 謝源，謝劍英，鄭小龍．混合有限月蘇下帶模糊交貨期的單機調(diào)度問題的研究[J]．信息與控制2005，34（3）：369-372．  

[14] Glover F. Future paths for integer programming and links to artificial intelligence[J]. Computer and Opreations. Research. 1986, 13:533-549.

[15] 盧冰原，陳華平，顧春生等，模糊環(huán)境下的柔性工作車間調(diào)度模型的研究[J]．運籌與管理．2004，13．

[16] 李福明，朱云龍，尹朝萬等.基于遺傳算法的模糊調(diào)度研究[J].信息與控制．2004，33（6）：703-708

[17] 吳儀，劉民等.JSSP基本約束特點分析及調(diào)度算法[J].清華大學(xué)學(xué)報(自然科學(xué)版)．2004，44(10)：

[18] Kinkpatric S, Gelatt CD, Vecchi M P.Operational by simulated annealing[J].Science.1983, 220:671-680.

[19] 吳梅，陸金桂.遺傳算法的研究進(jìn)展綜述[J]．機床與液壓．2008，36(3)．

[20] 孫卓明，余彬．遺傳算法．計算機時代．2004年，第1期

[21] 陳國良等．遺傳算法及應(yīng)用．北京：人民郵電出版社，1996

兩機無等待流水車間調(diào)度問題與仿真

摘    要

流水車間(Flow Shop)調(diào)度問題無論是在工廠經(jīng)營管理還是在產(chǎn)品制造中都具有廣泛的應(yīng)用，因此對流水車間調(diào)度問題進(jìn)行研究具有重大的理論意義和實際意義。

本文首先對車間調(diào)度問題國內(nèi)外研究現(xiàn)狀和發(fā)展趨勢進(jìn)行了系統(tǒng)的闡述。其次，對遺傳算法的基本理論進(jìn)行了詳細(xì)的論述。然后對Flow Shop調(diào)度問題建立數(shù)學(xué)模型。再次，在掌握了遺傳算法的基礎(chǔ)之上給出了基于遺傳算法求解Flow Shop調(diào)度問題的編碼方案，遺傳算子的設(shè)計。然后基于遺傳算法對調(diào)度問題進(jìn)行了實例分析。最后對上述兩種調(diào)度的結(jié)果進(jìn)行了分析，結(jié)果表明本文提出的方法是有效可行的。

關(guān)鍵詞：生產(chǎn)調(diào)度，流水車間調(diào)度，遺傳算法。

兩機無等待流水車間調(diào)度問題與仿真

ABSTRACT

Flow Shop (Flow Shop) scheduling problem in both factory management and has wide application in the product manufacturing, so the study of Flow Shop scheduling problem is of great theoretical significance and practical significance.This article first to the workshop scheduling problem research status and development trend at home and abroad systematically in this paper.Secondly, the basic theory of genetic algorithm in detail in this paper.Then the Flow Shop scheduling problem to establish mathematical model.Again, in the mastery of the genetic algorithm based on genetic algorithm is given based on the Flow Shop scheduling problem of coding scheme, the design of genetic operators.Then based on the genetic algorithm for scheduling problems on the instance analysis.Finally, the results of the two kinds of scheduling are analyzed, the results show that the proposed method is effective and feasible.

Key words: production scheduling;Flow shop scheduling;Genetic algorithm;

兩機無等待流水車間調(diào)度問題與仿真

目    錄

摘    要I

ABSTRACTII

目    錄III

第一章 緒    論1

1.1 引    言1

1.2 國內(nèi)外車間調(diào)度問題的研究現(xiàn)狀和存在的問題1

1.2.1 國內(nèi)外車間調(diào)度問題的研究現(xiàn)狀1

1.2.2 研究中存在的問題2

1.3 研究意義與目的3

1.4 本文的工作4

第二章 車間調(diào)度問題5

2.1. 車間調(diào)度問題的描述5

2.2 車間調(diào)度問題的特點6

2.3  車間調(diào)度問題的分類6

2.4  Job Shop 與Flow shop 比較7

2.5 調(diào)度問題的研究方法8

2.6 兩機無等待流水車間調(diào)度13

2.6.1生產(chǎn)周期的計算13

2.6.2生產(chǎn)周期的快速算法14

第三章 遺傳算法16

3.1 遺傳算法的形成與發(fā)展16

3.2 遺傳算法的基本思想17

3.3 遺傳算法的特點17

3.4 遺傳算法的過程和流程19

3.5 求解調(diào)度問題的遺傳算法22

3.5.1 遺傳算法的設(shè)計步驟22

3.5.2 編碼方式22

3.5.3 適配值函數(shù)24

3.5.4 遺傳算子的設(shè)計24

3.5.5 編碼參數(shù)26

3.5.6 遺傳算子26

3.5.7 算法的終止條件26

第四章 兩機無等待流水車間調(diào)度問題仿真27

4.1 流水車間調(diào)度問題的描述與數(shù)學(xué)模型27

4.2 基于Johnson法則的兩機無等待流水車間調(diào)度問題仿真28

4.3 遺傳算法的設(shè)計31

4.3.1 編碼方案31

4.3.2 群體的確定31

4.3.3 適應(yīng)度函數(shù)31

4.3.4 遺傳算子的設(shè)計31

4.4 基于遺傳算法的兩機無等待流水車間調(diào)度問題仿真32

4.5 結(jié)果分析32

第五章 全文總結(jié)33

參考文獻(xiàn)34

致 謝36

畢業(yè)設(shè)計小結(jié)37