中小型企業(yè)生產(chǎn)調(diào)度

1、中小型企業(yè)生產(chǎn)調(diào)度某中小企業(yè)車間生產(chǎn)調(diào)度咨詢題研究ResearchonProductionSchedulingProblemofWorkshopoftheSmallandMedium-sizedEnterprises學院：機械工程學院專業(yè)班級：學號：學生姓名：指導教師：年月摘要生產(chǎn)調(diào)度在任何企業(yè)中差不多上重要的，肩負著企業(yè)的日常生產(chǎn)運轉(zhuǎn)，起著組織、和諧、檢查、考核的職能。目前，制造業(yè)的競爭日益猛烈，在企業(yè)的日常運作過程中，會經(jīng)常遇到各種各樣的復(fù)雜的調(diào)度咨詢題，車間生產(chǎn)調(diào)度咨詢題解決的好壞直截了當阻礙著企業(yè)的運作效率和最終客戶中意程度。因此，調(diào)度咨詢題差不多成為運營治理領(lǐng)域的一大研究特點。對其進

2、行深入的研究具有重要的理論意義和實際意義。本文第一論述本文研究內(nèi)容的目的和意義，介紹了生產(chǎn)調(diào)度咨詢題在國內(nèi)外的研究現(xiàn)狀，分析了該領(lǐng)域中存在的咨詢題及進展趨勢。其次結(jié)合我國中小型企業(yè)的特點，研究了有關(guān)車間調(diào)度的差不多理論，并總結(jié)了車間生產(chǎn)調(diào)度的優(yōu)化方法和策略，分析和比較了各種生產(chǎn)調(diào)度算法的優(yōu)缺點，對車間調(diào)度咨詢題進行了描述，做出了生產(chǎn)調(diào)度咨詢題的改善。在幾種求解車間調(diào)度的方法中，著重介紹了啟發(fā)式方法中的palmer算法和彼得羅夫-哈姆算法。通過對沈陽亞中機械設(shè)備有限公司的車間調(diào)度咨詢題進行分析和研究，運用palmer算法和彼得羅夫-哈姆算法，對現(xiàn)有的排產(chǎn)順序進行改善，生產(chǎn)效率提升了28%，提升了

3、企業(yè)的競爭力。并對這兩種算法進行了比較與選優(yōu)，來講明生產(chǎn)調(diào)度方法的采納必須依具體車間的生產(chǎn)情形來確定。關(guān)鍵詞：中小企業(yè)；生產(chǎn)調(diào)度；彼得羅夫-哈姆算法；帕姆算法AbstractBasedonthesmallandmedium-sizedenterprisesintheworkshopinvestigation,atfirstthepurposeandmeaningofthisprojectarediscussed,andtheimportanceofshopproductionschedulingispresented,thetrendofthedomesticandoverseasresear

4、chofshopproduceandtheexistentproblemsinthisdomainareanalyzed.Secondlythebasictheoriesaboutshopschedulingarestudied,andtheoptimizingmeansandthestrategyofshopproductionschedulingaresummarized,thentheinterrelatedproblemsofshopschedulingaredescribed,andseveralheuristicmethodstosolveshopschedulingaresumm

5、arizedhere,andemphaticallyintroducedtheheuristicmethodincludespalmeralgorithmandPetrov-Hamalgorithm,andthroughthetwoalgorithmsforShenyangyazhongautomaticcontrolpotentialmanufacturingworkshopschedulingproblemandresearch,finallytothesetwoalgorithmsarecomparedwithexcellentproductionschedulingmethod,toi

6、llustratetheproductionworkshopinaccordancewithspecifictodetermine.Throughtheanalysis，weimprovethejob-shopschedulingproblembyusingthepalmerandPetrovHammalgorithm，enhancingtheefficiencyby28%,whichmaketheenterprisebecomestronger.Bycomparingthesetwoalgorithms,atthesametime,wehavenotonlyunderstandthemdee

7、ply,butrealizedchoosingsuitedschedulingalgorithmmustdependonthejob-shopenvironment.Keywords：Smallandmedium-sizedenterprises；Productionscheduling;Petrov-Hamalgorithm;Palmeralgorithm目錄摘要IAbstractIII第1章緒論11.1 課題研究的目的和意義11.1.1 本課題研究的目的11.1.2 本課題研究的意義21.2 國內(nèi)外現(xiàn)狀和進展趨勢21.2.1 國內(nèi)外研究現(xiàn)狀31.2.2 生產(chǎn)調(diào)度咨詢題研究的進展趨勢41.3

8、 本課題的要緊研究內(nèi)容5第2章中小型企業(yè)車間生產(chǎn)調(diào)度的差不多理論72.1 車間調(diào)度的定義72.2 車間調(diào)度咨詢題的概述82.2.1 車間生產(chǎn)調(diào)度咨詢題的含義82.2.2 車間生產(chǎn)調(diào)度的類型92.2.3 車間生產(chǎn)調(diào)度的特點102.3 車間生產(chǎn)調(diào)度咨詢題的研究策略112.4 中小企業(yè)車間生產(chǎn)調(diào)度咨詢題研究122.4.1 中小企業(yè)的定義122.4.2 我國中小企業(yè)的特點152.4.3 中小企業(yè)生產(chǎn)調(diào)度的要緊咨詢題16第3章車間生產(chǎn)的調(diào)度方法研究183.1 傳統(tǒng)的優(yōu)化理論與方法183.2 啟發(fā)式方法193.3 基于知識的調(diào)度方法253.4 車間生產(chǎn)調(diào)度方法的比較及其評判28第4章案例分析314.1 企

9、業(yè)背景概述314.2 車間生產(chǎn)調(diào)度的治理結(jié)構(gòu)314.3 機械加工車間的現(xiàn)狀分析324.4 生產(chǎn)調(diào)度排序改善的案例334.4.1 梁板334.4.2 基于palmer算法零件排序咨詢題求解364.4.3 基于彼得羅夫-哈姆算法零件排序咨詢題求解374.5 總結(jié)39第5章結(jié)論41參考文獻42第1章緒論調(diào)度咨詢題來源于不同的領(lǐng)域，如柔性制造系統(tǒng)，生產(chǎn)打算，運算機設(shè)計，后勤及通訊等。生產(chǎn)調(diào)度，即對生產(chǎn)過程進行打算，作為一個關(guān)鍵模塊，是整個先進生產(chǎn)制造系統(tǒng)實現(xiàn)治理技術(shù)、運籌技術(shù)、優(yōu)化技術(shù)、自動化與運算機技術(shù)進展的核心。有效的調(diào)度方法及其優(yōu)化的研究與應(yīng)用，是實現(xiàn)先進制造和提升生產(chǎn)效益的基礎(chǔ)和關(guān)鍵，可大大提

10、升生產(chǎn)效益和資源利用率，進而增強企業(yè)的競爭能力。生產(chǎn)調(diào)度咨詢題是一個資源分配咨詢題，只只是那個地點的資源是設(shè)備而己。其目的是使工件加工路徑的組合優(yōu)化，確定工件的加工路徑和每一工序的加工開始時刻，以確保所選定的生產(chǎn)目標最優(yōu)，如總加工時刻最短等.由于制造系統(tǒng)中每個零件的生產(chǎn)工藝不同，所需的加工設(shè)備、加工時刻、要求的交貨期和生產(chǎn)數(shù)量的不同，使得生產(chǎn)調(diào)度咨詢題成為自動化制造系統(tǒng)研究中的一個難點和熱點。車間生產(chǎn)調(diào)度在企業(yè)生產(chǎn)經(jīng)營活動中占有十分重要的地位，生產(chǎn)調(diào)度系統(tǒng)也是CIMS(ComputerIntegratedManufacturingSystems),ERP(EnterpriseResourceP

11、lanning)等系統(tǒng)中的重要組成部分，因此受到學術(shù)界和工業(yè)界的廣泛關(guān)注，對它的研究具有專門高的理論意義和實際意義1。1.1 課題研究的目的和意義1.1.1 本課題研究的目的調(diào)度決策水平的提升差不多成為現(xiàn)代企業(yè)生產(chǎn)經(jīng)營過程能否穩(wěn)固高效運轉(zhuǎn)的決定性因素之一，因此，對生產(chǎn)調(diào)度理論的研究、優(yōu)化生產(chǎn)調(diào)度的算法研究及應(yīng)用系統(tǒng)軟件的開發(fā)，都受到學術(shù)界和企業(yè)界的深切關(guān)注。近年來，諸如并行加工、精益生產(chǎn)、準時制生產(chǎn)、異地制造、動態(tài)聯(lián)盟等新模式的持續(xù)提出，為信息技術(shù)的應(yīng)用和治理方法的提升指出了更多的新方向。這些新的生產(chǎn)治理模式的顯現(xiàn)則要求運用現(xiàn)代生產(chǎn)方式相適應(yīng)的先進生產(chǎn)治理方法及調(diào)度技術(shù)。因此，改進型生產(chǎn)治理模

12、式對提升生產(chǎn)效率有專門大助益。有史以來，有限資源的合理配置和優(yōu)化利用咨詢題始終是人類社會所面臨的最差不多經(jīng)濟咨詢題，那個咨詢題貫穿于社會生活的各個方面。從一個國家、社會的宏觀經(jīng)濟運行到具體企業(yè)的微觀經(jīng)濟活動，都要受資源條件的限制。對企業(yè)來講，能否對現(xiàn)有資源進行合理配置和充分利用將直截了當阻礙到產(chǎn)品的制造成本，進而成為阻礙企業(yè)效益的重要因素。企業(yè)資源的合理配置和優(yōu)化利用專門大程度上體現(xiàn)在車間一層的生產(chǎn)活動中，因此加大車間層的生產(chǎn)打算與操縱一直在企業(yè)生產(chǎn)經(jīng)營活動中占有十分重要的地位。車間生產(chǎn)調(diào)度是制造系統(tǒng)生產(chǎn)治理的核心，生產(chǎn)治理任務(wù)順利實施與完成，最終要靠合理的生產(chǎn)調(diào)度來保證2。車間生產(chǎn)調(diào)度研究的

13、是如何合理地配置加工過程的各種資源，減少零件的加工預(yù)備、等待與傳送時刻，從而提升設(shè)備利用率與生產(chǎn)效率，降低生產(chǎn)成本。因此，及時準確的生產(chǎn)調(diào)度對生產(chǎn)系統(tǒng)的高效運行有著重要的阻礙，要緊表現(xiàn)在生產(chǎn)調(diào)度能夠保證生產(chǎn)打算的有效實施:高效低耗地使用生產(chǎn)資源;均衡生產(chǎn)，減少在制品的資金占用等。1.1.2 本課題研究的意義生產(chǎn)打算與調(diào)度環(huán)節(jié)是企業(yè)生產(chǎn)治理的核心，也是整個企業(yè)治理最煩瑣和最難治理的環(huán)節(jié)。隨著工業(yè)生產(chǎn)過程的日益復(fù)雜與規(guī)模的大型化，要求運算機系統(tǒng)不僅要完成直截了當面向過程的操縱和優(yōu)化，而且要在獵取生產(chǎn)全部過程信息基礎(chǔ)上，進行指揮調(diào)度和綜合治理。生產(chǎn)調(diào)度的優(yōu)化是先進制造技術(shù)和現(xiàn)代治理技術(shù)的核心技術(shù)。優(yōu)

14、化生產(chǎn)打算與調(diào)度成為增強企業(yè)競爭力、提升企業(yè)經(jīng)濟效益和社會效益的關(guān)鍵因素。因而研究制造行業(yè)大規(guī)模復(fù)雜生產(chǎn)過程的生產(chǎn)調(diào)度咨詢題與方法關(guān)于提升企業(yè)的治理水平，增強企業(yè)的競爭力，促進整個行業(yè)的進步與進展具有十分重要的意義。目前，國內(nèi)的大部分企業(yè)要緊依靠體會豐富的調(diào)度員手工安排調(diào)度打算。關(guān)于調(diào)度咨詢題比較簡單的情形下這種方法依舊可行的，然而，在調(diào)度任務(wù)規(guī)模較大且動態(tài)多變的環(huán)境中，單純的手工調(diào)度就顯得低效甚至無能為力了，況且，關(guān)于企業(yè)來講，體會豐富的調(diào)度員本身確實是一種稀缺資源。明顯，充分利用目前己取得的理論研究成果，改善車間調(diào)度咨詢題，關(guān)心企業(yè)提升排產(chǎn)效率，關(guān)于我國的生產(chǎn)有著重要的現(xiàn)實意義。1.2 國

15、內(nèi)外現(xiàn)狀和進展趨勢1.2.1 國內(nèi)外研究現(xiàn)狀隨著科學技術(shù)的快速進展，專門是網(wǎng)絡(luò)技術(shù)、通訊技術(shù)、運算機技術(shù)等現(xiàn)代科技以及有關(guān)基礎(chǔ)行業(yè)的技術(shù)進步，使傳統(tǒng)意義上的時刻和空間距離日益被拉近縮短，市場趨向全球一體化，市場競爭轉(zhuǎn)型為異地、跨區(qū)域、甚至跨國競爭等，猛烈的市場競爭使產(chǎn)品的更新代換日趨頻繁、種類越來越復(fù)雜，因而要求制造系統(tǒng)既能有效地進行多品種、小批量的生產(chǎn)，又有較高的自動化程度和生產(chǎn)效率，以適應(yīng)多變的市場環(huán)境和客戶需求。這就意味著有關(guān)企業(yè)在具有較高生產(chǎn)率、較好質(zhì)量保證能力的同時，也要具有快速的響應(yīng)市場變化和需求增長的能力，努力使制造單元具有剛性生產(chǎn)線的效率和工作車間的柔性，才能使企業(yè)適應(yīng)猛烈的市

16、場競爭。為了加大和改善生產(chǎn)治理模式，提升加工單元（包括加工車間）的柔性及響應(yīng)市場需求速度，在許多企業(yè)中生產(chǎn)調(diào)度（專門是具體到車間調(diào)度）當前仍舊采納本地化、單機實現(xiàn)模式，乃至人工方式進行。早在1954年，Johnson就對兩臺機床的FlowShop型調(diào)度咨詢題進行了研究，并提出了一個簡便而又相當巧妙的算法。他的研究成果引起了學術(shù)界的濃厚愛好。因此，學術(shù)界試圖將他的結(jié)果推廣到三臺或是更多的機器上去，然而都沒有成功。直到1977年，才有研究證明三臺以上機床的FlowShop調(diào)度咨詢題是一個NP完備咨詢題。由于車間調(diào)度在調(diào)度咨詢題中具有代表性，專門多領(lǐng)域的學者都能夠把各自領(lǐng)域的組合優(yōu)化咨詢題抽象為車間

17、調(diào)度咨詢題。因此，眾多學者就車間調(diào)度咨詢題展開了深入廣泛的研究。國外對車間治理系統(tǒng)的研究要緊著重于對FMS的應(yīng)用研究，因為一些制造企業(yè)，如飛機或汽車制造公司，資金力量和科技力量較為雄厚，它們直截了當進行了有關(guān)FMS的研究與開發(fā)，同時取得了較為明顯的成效例如美國底特律市郊的魯奇工廠是汽車制造的傳統(tǒng)中心之一，這家工廠一直是福特公司的總裁兼首席執(zhí)行官、亨利的曾孫比爾福特的商業(yè)理念的實踐場所。但現(xiàn)在它看起來發(fā)生著戲劇性的變化：比爾福特差不多斥資20億元改造該公司慢慢老化的那個制造中心，他正設(shè)法建立精簡靈活的生產(chǎn)線，并使其能夠成為現(xiàn)代汽車的生產(chǎn)進展方向。日本的本田公司在靈活生產(chǎn)的道路上可能走得最遠，不僅

18、本田公司所有的汽車工廠都能生產(chǎn)幾種車型的汽車，而且現(xiàn)在各個分廠還能迅速實現(xiàn)裝配不同車型的轉(zhuǎn)換。在底特律一家工廠要4到6周才能改變生產(chǎn)的汽車車型，重裝自動機械裝置和其它工具。而本田公司現(xiàn)在能一夜間完成這一項工作，它只需要簡單地更換操縱自動機械裝置的有關(guān)軟件。盡管，這是多方面因素的綜合結(jié)果，例如全球供應(yīng)鏈等因素，但如果本田公司沒有采納靈活多變的FMS,就不可能有如此快的響應(yīng)速度3。在對車間調(diào)度咨詢題進行的研究中，有許多方法在各種各樣的有關(guān)決策的期刊中被報道，它們在不同程度上都獲得了成功。這些方法無一例外地吸取了近35年來的一系列先進技術(shù)。這些技術(shù)包括數(shù)學規(guī)劃(mathematicalprogram

19、ming),專家系統(tǒng)(expertsystems)神經(jīng)網(wǎng)絡(luò)(neuralnetworks)、遺傳算法(geneticalgorithms)和模糊邏輯(fuzzylogic)等。不同學科的交叉，帶來了車間調(diào)度領(lǐng)域眾多的新興理論和新方法。國內(nèi)對車間治理軟件的研究起步較晚，目前盡管大部分工廠都在實施ERP軟件系統(tǒng)，由于技術(shù)上的制約，它們?nèi)耘f沒有找到好的車間作業(yè)調(diào)度方法，差不多上是靠調(diào)度人員的體會進行車間作業(yè)分配和調(diào)度。隨著遺傳算法在作業(yè)調(diào)度方面的應(yīng)用，我國“八五”期間也有一些高校和研究機構(gòu)，例如清華大學、上海交通大學、西安交通大學、北京機械工業(yè)自動化研究所等進行此類咨詢題的研究，并已開發(fā)出相應(yīng)的運算

20、機輔助生產(chǎn)調(diào)度與治理系統(tǒng)，逐步從理論研究時期走向應(yīng)用時期.隨著各種專門調(diào)度咨詢題的攻克和新方法、新設(shè)備的顯現(xiàn)，車間調(diào)度研究正在向動態(tài)、靈敏、多資源、智能化的方向進展4。1.2.2 生產(chǎn)調(diào)度咨詢題研究的進展趨勢盡管對車間調(diào)度領(lǐng)域的研究已有幾十年的歷史，但至今尚未形成一套系統(tǒng)的方法與理論，同時多數(shù)研究忽略了專門多重要的因素，建模時對真實環(huán)境進行了大量的簡化，離應(yīng)用尚有不小的差距。車間制造系統(tǒng)的建模與描述是研究調(diào)度咨詢題的動身點，由于制造過程的復(fù)雜性，且純仿真模型、數(shù)學規(guī)劃、操縱論、圖與網(wǎng)絡(luò)的建模方法各有優(yōu)缺點，因此目前尚難建立一個專門有效的模型。且現(xiàn)行的研究大多只關(guān)懷工件的調(diào)度咨詢題，而對其他資源

21、分配咨詢題像刀具、物料儲運系統(tǒng)的研究不多5。因此，以后的進一步研究，我們能夠從生產(chǎn)調(diào)度的有關(guān)模型中得到啟發(fā)（如異地生產(chǎn)調(diào)度咨詢題的深入研究）；此外一樣來講，調(diào)度方法的搜索效率和搜索成效是相互矛盾、相互制約的，通常按照實際情形，需要在兩者之間做出折衷的選擇?？傊?，對車咨詢調(diào)度領(lǐng)域這一個有NPhard特性的研究，隨著應(yīng)用數(shù)學理論的進一步進展，必定朝著集成化、多目標化、動態(tài)有用化、高度次優(yōu)化方向深入進行。1.3 本課題的要緊研究內(nèi)容車間生產(chǎn)調(diào)度咨詢題是企業(yè)生產(chǎn)運作治理中最復(fù)雜、最棘手的咨詢題。從理論上講，人們通過長期的實踐摸索出了許許多多的生產(chǎn)調(diào)度方法，而本論文的研究不可能也不必要窮盡一切理論，課題

22、研究的要緊內(nèi)容是生產(chǎn)調(diào)度咨詢題的描述方法，流水線車間調(diào)度差不多理論和調(diào)度方法，并針對我國中小型企業(yè)車間生產(chǎn)調(diào)度治理的實際情形，摸索如何應(yīng)用先進有用的生產(chǎn)調(diào)度方法去解決企業(yè)長期存在的一些咨詢題。本文總體上是按照如下的線索逐步進行的：緒論，車間生產(chǎn)調(diào)度的差不多理論，車間生產(chǎn)調(diào)度的研究方法與評判，應(yīng)用案例分析，全文總結(jié)。第一章為緒論，為全文的綱領(lǐng)，介紹了課題的研究背景、研究目的和研究意義。第二章是對車間生產(chǎn)調(diào)度理論知識的研究介紹，由淺入深，由基礎(chǔ)的知識概念入手，循序漸進到中小企業(yè)的生產(chǎn)調(diào)度咨詢題，最后具體到提出生產(chǎn)調(diào)度的咨詢題描述有關(guān)咨詢題，包括生產(chǎn)調(diào)度的分類、特點、研究策略。第三章要緊內(nèi)容是基于車

23、間生產(chǎn)調(diào)度咨詢題的研究方法，包括數(shù)學規(guī)劃法、啟發(fā)式方法、運算智能調(diào)度方法。要緊研究啟發(fā)式方法中的彼得羅夫-哈姆算法和palmer算法。并通過調(diào)度方法的比較和評判來講明調(diào)度方法的相對權(quán)重。第四章是對沈陽亞中機械設(shè)備有限公司運用車間調(diào)度方法來對該企業(yè)的零件加工進行改善，并應(yīng)用彼得羅夫-哈姆算法和palmer算法來驗證算法的可行性，同時對這兩種算法進行選優(yōu)，并對該企業(yè)車間調(diào)度狀況進行分析，提出相應(yīng)意見。第2章中小型企業(yè)車間生產(chǎn)調(diào)度的差不多理論2.1 車間調(diào)度的定義車間調(diào)度確實是按照加工對象的加工需求，運用不同的調(diào)度決策規(guī)則,規(guī)劃系統(tǒng)的加工事件，并按照優(yōu)化結(jié)果形成最佳的生產(chǎn)加工順序，同時實現(xiàn)設(shè)備集和任

24、務(wù)集的合理最優(yōu)化結(jié)合6,如圖2-1所示。圖2-1生產(chǎn)調(diào)度咨詢題的傳統(tǒng)定義實際生產(chǎn)調(diào)度咨詢題盡管不能簡單地歸結(jié)為上述的排序咨詢題，然而差不多上以這一咨詢題作為基礎(chǔ)的。與經(jīng)典調(diào)度理論中的生產(chǎn)調(diào)度咨詢題有關(guān)的差不多概念要緊有：1）加工任務(wù)加工任務(wù)通常是一組n個等待調(diào)度以便進行加工的工件或者原材料。在其他有關(guān)文獻中叫法不一，有的稱作要加工的工件，有的稱作要生產(chǎn)的產(chǎn)品，我們在本文中統(tǒng)稱為加工任務(wù)。2）機器機器指的是執(zhí)行加工任務(wù)的一組生產(chǎn)設(shè)備或生產(chǎn)單元，各臺機器都有自己的生產(chǎn)能力約束。3）工序工序指的是某個工件或者產(chǎn)品的工藝路線，也確實是加工任務(wù)在一組機器上的執(zhí)行順序。4）時刻參數(shù)與加工任務(wù)和機器有關(guān)的各

25、種時刻參數(shù)，如加工任務(wù)的預(yù)備時刻、等待時刻、打算完工時刻、實際完工時刻、拖期時刻、交貨時刻、在某個機器上的加工時刻以及機器的閑暇時刻等。5）性能指標生產(chǎn)調(diào)度方案要達到的性能指標，如完工時刻目標（最大流程時刻、平均流程時刻、最大完工時刻、平均完工時刻等）、交貨期目標、成本目標和機器利用率目標等。6）操縱參數(shù)與物料供應(yīng)和投入有關(guān)的各種參數(shù)，如物料供應(yīng)的限制約束、物料投入生產(chǎn)的時刻、地點、速度和數(shù)量等。7）調(diào)度規(guī)則調(diào)度規(guī)則指的是一組操縱生產(chǎn)過程的規(guī)則，要緊有生產(chǎn)時序操縱規(guī)則（各種優(yōu)先規(guī)則）、中間儲備利用率調(diào)劑規(guī)則和生產(chǎn)代價調(diào)劑規(guī)則等。8）調(diào)度算法調(diào)度算法的目的確實是要綜合考慮調(diào)度咨詢題所提出的一些具

26、體要求，用數(shù)學的語言來表達這些要求，在給定時刻參數(shù)和調(diào)度規(guī)則條件下，確定各種操縱參數(shù)，使得一種或多種性能指標最優(yōu)7。2.2 車間調(diào)度咨詢題的概述車間調(diào)度咨詢題一樣能夠描述為:n個工件在m臺機器上加工，一個工件分為k道工序，每道工序能夠在若干臺機器上加工;每一臺機器在每個時刻只能加工某個工件的某道工序，且只能在上道工序加工完成后才能開始下一道工序的加工。前者稱為占用約束，后者稱為順序約束。2.2.1 車間生產(chǎn)調(diào)度咨詢題的含義車間生產(chǎn)調(diào)度確實是對一個可用的加工機床集在時刻上進行加工任務(wù)的分配，以滿足一個性能指標集8。典型的車間生產(chǎn)調(diào)度咨詢題包括一個要完成的作業(yè)集，每項作業(yè)由一個作業(yè)集組成。各操作的

27、完成需要占用機床或其它資源，同時必須按一個可行的工藝次序進行加工;每臺機床可加工零件的若干操作，同時在不同機床能加工的操作集能夠不同。在約束條件下，調(diào)度的目標是將作業(yè)合理地安排到各機床，并合理安排作業(yè)的加工次序和加工開始時刻，同時優(yōu)化一些性能指標。在實際車間生產(chǎn)調(diào)度中，一樣需要考慮兩個方面的調(diào)度咨詢題，一是生產(chǎn)作業(yè)的調(diào)度，二是生產(chǎn)資源的分配。目前大部分研究集中在生產(chǎn)作業(yè)調(diào)度上，沒有考慮資源分配，而將資源作為約束處理。廠級編制的車間作業(yè)打算，給出了各種零件、部件的投入產(chǎn)出進度安排，但還不是車間的執(zhí)行打算。車間還要對各項任務(wù)的作業(yè)順序合理安排，分派各班組、各工作地的任務(wù)，以便在完成打算任務(wù)的前提下

28、，縮短生產(chǎn)周期，均衡設(shè)備負荷，提升操作人員的工作效率，取得良好的經(jīng)濟效益.生產(chǎn)作業(yè)的這種細節(jié)安排是車間生產(chǎn)調(diào)度操縱的重要一環(huán)，它建立了打算與生產(chǎn)操縱間的直截了當聯(lián)系，是廠級各車間生產(chǎn)治理人員所必須研究的一個更重要的課題。2.2.2 車間生產(chǎn)調(diào)度的類型生產(chǎn)調(diào)度要緊是在生產(chǎn)作業(yè)打算的基礎(chǔ)上確定生產(chǎn)任務(wù)的加工順序以及各種制造資源的實時動態(tài)調(diào)度9。確定生產(chǎn)任務(wù)的加工順序為作業(yè)排序咨詢題，它有不同的分類方法：1）生產(chǎn)來源按照需求產(chǎn)生的來源將車間可分為開環(huán)車間和閉環(huán)車間。2）加工系統(tǒng)的復(fù)雜度按照加工系統(tǒng)的復(fù)雜度能夠?qū)⑵浞譃閱闻_處理機、多臺并行機、車間作業(yè)調(diào)度（JobShop沐口流水車間調(diào)度（FlowSho

29、p）。單臺處理機調(diào)度（SingleShop）:在這種車間中，每個零件只能有一道工序。單機調(diào)度咨詢題是最簡單的形式，在這種情形下，要求每個加工任務(wù)都要在一臺機器上執(zhí)行一次，為此存在任務(wù)的優(yōu)化排隊咨詢題。多臺并行機調(diào)度:井行機調(diào)度咨詢題與單機調(diào)度咨詢題有些相似，不同的是每個加工任務(wù)能夠在任意一臺機器上加工一次，它比單機調(diào)度咨詢題的優(yōu)化咨詢題更為突出。車間作業(yè)調(diào)度（JobShop）:這是最一樣的調(diào)度類型，并不限制作業(yè)操作的加工設(shè)備，并承諾一個加工任務(wù)具有不同的加工路徑，在這種車間中，機床設(shè)備的布局能夠是任意的，因此零件的加工路徑也是任意的，同時各零件的工序內(nèi)容和數(shù)量也是任意的。流水車間調(diào)度(Flow

30、Shop):這種調(diào)度咨詢題假設(shè)每個加工任務(wù)都要在所有工序中的機器上加工一次，并有一致的加工操作和加工順序;在這種車間中，每個零件都有相同的加工路徑。如此，機床設(shè)備的布局如同流水線一樣，零件依一次從流水線的一端流進，最后從另一端流出。3)性能指標按照性能指標能夠分為基于調(diào)度費用和調(diào)度性能的指標。4)生產(chǎn)環(huán)境按照生產(chǎn)環(huán)境的特點將調(diào)度咨詢題分為確定性調(diào)度和隨機性調(diào)度。5)加工特點加工任務(wù)或被加工工件的特點要緊表述為加工任務(wù)或者被加工工件是否有優(yōu)先制約、以及其他各種類型的約束條件、任意開釋期或等開釋期、任意加工時刻或單位加工時刻、加工任務(wù)是否需要拆分和組合等。按照這一點能夠把生產(chǎn)調(diào)度咨詢題分為靜態(tài)調(diào)度

31、咨詢題和動態(tài)調(diào)度咨詢題兩大類。靜態(tài)車間調(diào)度(StaticScheduling):靜態(tài)調(diào)度是指所有待安排加工的加工任務(wù)或工件均處于待加工狀態(tài)，進行一次調(diào)度之后，各個加工任務(wù)或工件的加工順序就被確定，在以后的加工過程中就不再改變。車間的調(diào)度不考慮零件在加工過程中顯現(xiàn)的意外情形，如機床突然損壞、零件的交貨期提早、有更緊迫的零件要求被加工等等。動態(tài)車間調(diào)度(DynamicScheduilng):動態(tài)調(diào)度是指加工任務(wù)或工件依次進入待加工狀態(tài)，各個加工任務(wù)或工件持續(xù)進入系統(tǒng)同意加工，同時完成加工的加工任務(wù)或工件又持續(xù)離開，還要考慮加工環(huán)境中持續(xù)顯現(xiàn)的不可推測的動態(tài)擾動，如操作的超時和設(shè)備的損壞等，因此動態(tài)

32、調(diào)度要按照系統(tǒng)中加工任務(wù)或工件、設(shè)備等的狀況，持續(xù)地進行調(diào)度。6)是否有序按照調(diào)度是否有序能夠講價共分為有序加工和無序加工。2.2.3 車間生產(chǎn)調(diào)度的特點1）復(fù)雜性一是生產(chǎn)因素的多樣與復(fù)雜，車間中工件、機器、緩存和搬運系統(tǒng)之間相互阻礙、相互作用。每個工件又要考慮它的加工時刻、安裝時刻和操作順序等因素，因而相當復(fù)雜;二是調(diào)度咨詢題是在等式或不等式約束下求指標的優(yōu)化，在運算量上往往是NP完全咨詢題，隨著咨詢題規(guī)模的增大，其運算量急劇增加，使得一些常規(guī)的方法無能為力，關(guān)于這一點差不多被證明。因此調(diào)度咨詢題往往沒有精確的解，通常是在解答過程中尋求其最優(yōu)解10。2）隨機性車間調(diào)度中有專門多隨機和不確定因

33、素，如工件到達時刻的不確定性，實際工件的加工時刻也有一定的隨機性。而且生產(chǎn)系統(tǒng)中常有突發(fā)偶然事件，如機器出故障、作業(yè)交貨期的改變、急件插入和人員誤操作等不可預(yù)見因素，生產(chǎn)調(diào)度需要按照生產(chǎn)情形做出動態(tài)調(diào)整。3）約束性車間調(diào)度咨詢題中資源的數(shù)量、緩存的容量、工件到期時刻以及工件的操作順序等差不多上約束。此外還有一些人為的因素，如要求各機器上的負荷要平穩(wěn)等。4）多目標車間生產(chǎn)調(diào)度往往是多目標的，可分為基于作業(yè)交貨期的目標、基于作業(yè)完成時刻的目標和基于生產(chǎn)成本的目標，而且這些目標之間往往是有沖突的。2.3 車間生產(chǎn)調(diào)度咨詢題的研究策略調(diào)度策略是車間調(diào)度高層次的決策部分，由于調(diào)度咨詢題的復(fù)雜性，因而在實

34、際的研究過程中逐步形成了不同的調(diào)度策略支持，大致可分為以下幾種。1）并行或分布策略。適應(yīng)不同車間操縱結(jié)構(gòu)與調(diào)度咨詢題復(fù)雜性的實際需要，許多學者提出并行或分布策略來解決調(diào)度咨詢題。2）分解與成組策略。利用分解生產(chǎn)打算或GT的調(diào)度策略能夠大大降低咨詢題的運算復(fù)雜性和規(guī)模，求得調(diào)度咨詢題的較優(yōu)解，同時優(yōu)化系統(tǒng)的一些性能指標，GT和獨立制造島的應(yīng)用實踐便是一個明顯的例證。3）人機協(xié)同策略。調(diào)度咨詢題的性質(zhì)、現(xiàn)有研究方法的缺陷以及人類專門的思維能力決定了人機協(xié)同策略的生命力。大量的研究成果表明：人機協(xié)同交互的策略能夠減少系統(tǒng)的搜索空間，可在有限時刻、背景知識條件下解決困難的咨詢題。4）實時或動態(tài)重調(diào)度策

35、略。車間制造過程的隨機性、不確定性需要持續(xù)地進行重調(diào)度，以處理突發(fā)的事件?；谀壳暗难芯?，關(guān)于動態(tài)調(diào)度的具體策略有：周期調(diào)度，連續(xù)調(diào)度，事件驅(qū)動調(diào)度，周期與事件驅(qū)動混合調(diào)度，周期與連續(xù)調(diào)度混合的策略等。5）生產(chǎn)打算與調(diào)度集成策略。生產(chǎn)打算、調(diào)度的集成研究具有全局優(yōu)化的特點，也符合先進制造模式的思想。6）多目標權(quán)衡決策。實際調(diào)度咨詢題是多目標的，且這些目標往往相互沖突。關(guān)于此類多目標優(yōu)化咨詢題，常用數(shù)學規(guī)劃中的約束法、評判函數(shù)法、分層序列法（AHP）、功效函數(shù)法等。2.4 中小企業(yè)車間生產(chǎn)調(diào)度咨詢題研究2.4.1 中小企業(yè)的定義不同國家、不同經(jīng)濟進展的時期、不同行業(yè)對其界定的標準不盡相同，且隨著

36、經(jīng)濟的進展而動態(tài)變化。各國一樣從質(zhì)和量兩個方面對中小企業(yè)進行定義，質(zhì)的指標要緊包括企業(yè)的組織形式、融資方式及所處行業(yè)地位等，量的指標則要緊包括雇員人數(shù)、實收資本、資產(chǎn)總值等。量的指標較質(zhì)的指標更為直觀，數(shù)據(jù)選取容易，大多數(shù)國家都以量的標準進行劃分，如美國國會2001年出臺的美國小企業(yè)法對中小企業(yè)的界定標準為雇員人數(shù)不超過500人，英國、歐盟等在采取量的指標的同時，也以質(zhì)的指標作為輔助11。按照第九屆全國人民代表大會常務(wù)委員會第二十八次會議于2002年6月29日通過的中華人民共和國中小企業(yè)促進法的精神，工業(yè)和信息化部、國家統(tǒng)計局、國家進展和改革委員會財政部于2011年6月18日公布了中小企業(yè)劃型

37、標準規(guī)定，對要緊行業(yè)的中小企業(yè)的標準作出了明確的界定。該標準是按照企業(yè)職工人數(shù)、銷售額、資產(chǎn)總額等指標，結(jié)合行業(yè)特點制定的。按照通知的規(guī)定，不同行業(yè)的中小企業(yè)應(yīng)該按照以下標準認定：1）工業(yè)。從業(yè)人員1000人以下或營業(yè)收入40000萬元以下的為中小微型企業(yè)。其中，從業(yè)人員300人及以上，且營業(yè)收入2000萬元及以上的為中型企業(yè)；從業(yè)人員20人及以上，且營業(yè)收入300萬元及以上的為小型企業(yè)；從業(yè)人員20人以下或營業(yè)收入300萬元以下的為微型企業(yè)。2）農(nóng)、林、牧、漁業(yè)。營業(yè)收入20000萬元以下的為中小微型企業(yè)。其中，營業(yè)收入500萬元及以上的為中型企業(yè)，營業(yè)收入50萬元及以上的為小型企業(yè)，營業(yè)收

38、入50萬元以下的為微型企業(yè)。3）建筑業(yè)。營業(yè)收入80000萬元以下或資產(chǎn)總額80000萬元以下的為中小微型企業(yè)。其中，營業(yè)收入6000萬元及以上，且資產(chǎn)總額5000萬元及以上的為中型企業(yè)；營業(yè)收入300萬元及以上，且資產(chǎn)總額300萬元及以上的為小型企業(yè)；營業(yè)收入300萬元以下或資產(chǎn)總額300萬元以下的為微型企業(yè)。4）批發(fā)業(yè)。從業(yè)人員200人以下或營業(yè)收入40000萬元以下的為中小微型企業(yè)。其中，從業(yè)人員20人及以上，且營業(yè)收入5000萬元及以上的為中型企業(yè)；從業(yè)人員5人及以上，且營業(yè)收入1000萬元及以上的為小型企業(yè)；從業(yè)人員5人以下或營業(yè)收入1000萬元以下的為微型企業(yè)。5）零售業(yè)。從業(yè)人員

39、300人以下或營業(yè)收入20000萬元以下的為中小微型企業(yè)。其中，從業(yè)人員50人及以上，且營業(yè)收入500萬元及以上的為中型企業(yè)；從業(yè)人員10人及以上，且營業(yè)收入100萬元及以上的為小型企業(yè)；從業(yè)人員10人以下或營業(yè)收入100萬元以下的為微型企業(yè)。6）交通運輸業(yè)。從業(yè)人員1000人以下或營業(yè)收入30000萬元以下的為中小微型企業(yè)。其中，從業(yè)人員300人及以上，且營業(yè)收入3000萬元及以上的為中型企業(yè)；從業(yè)人員20人及以上，且營業(yè)收入200萬元及以上的為小型企業(yè)；從業(yè)人員20人以下或營業(yè)收入200萬元以下的為微型企業(yè)。7）倉儲業(yè)。從業(yè)人員200人以下或營業(yè)收入30000萬元以下的為中小微型企業(yè)。其中

40、，從業(yè)人員100人及以上，且營業(yè)收入1000萬元及以上的為中型企業(yè)；從業(yè)人員20人及以上，且營業(yè)收入100萬元及以上的為小型企業(yè)；從業(yè)人員20人以下或營業(yè)收入100萬元以下的為微型企業(yè)。8）郵政業(yè)。從業(yè)人員1000人以下或營業(yè)收入30000萬元以下的為中小微型企業(yè)。其中，從業(yè)人員300人及以上，且營業(yè)收入2000萬元及以上的為中型企業(yè)；從業(yè)人員20人及以上，且營業(yè)收入100萬元及以上的為小型企業(yè)；從業(yè)人員20人以下或營業(yè)收入100萬元以下的為微型企業(yè)。9）住宿業(yè)。從業(yè)人員300人以下或營業(yè)收入10000萬元以下的為中小微型企業(yè)。其中，從業(yè)人員100人及以上，且營業(yè)收入2000萬元及以上的為中型

41、企業(yè)；從業(yè)人員10人及以上，且營業(yè)收入100萬元及以上的為小型企業(yè)；從業(yè)人員10人以下或營業(yè)收入100萬元以下的為微型企業(yè)。10）餐飲業(yè)。從業(yè)人員300人以下或營業(yè)收入10000萬元以下的為中小微型企業(yè)。其中，從業(yè)人員100人及以上，且營業(yè)收入2000萬元及以上的為中型企業(yè)；從業(yè)人員10人及以上，且營業(yè)收入100萬元及以上的為小型企業(yè)；從業(yè)人員10人以下或營業(yè)收入100萬元以下的為微型企業(yè)。11）信息傳輸業(yè)。從業(yè)人員2000人以下或營業(yè)收入100000萬元以下的為中小微型企業(yè)。其中，從業(yè)人員100人及以上，且營業(yè)收入1000萬元及以上的為中型企業(yè)；從業(yè)人員10人及以上，且營業(yè)收入100萬元及以

42、上的為小型企業(yè)；從業(yè)人員10人以下或營業(yè)收入100萬元以下的為微型企業(yè)。12）軟件和信息技術(shù)服務(wù)業(yè)。從業(yè)人員300人以下或營業(yè)收入10000萬元以下的為中小微型企業(yè)。其中，從業(yè)人員100人及以上，且營業(yè)收入1000萬元及以上的為中型企業(yè)；從業(yè)人員10人及以上，且營業(yè)收入50萬元及以上的為小型企業(yè)；從業(yè)人員10人以下或營業(yè)收入50萬元以下的為微型企業(yè)。13）房地產(chǎn)開發(fā)經(jīng)營。營業(yè)收入200000萬元以下或資產(chǎn)總額10000萬元以下的為中小微型企業(yè)。其中，營業(yè)收入1000萬元及以上，且資產(chǎn)總額5000萬元及以上的為中型企業(yè)；營業(yè)收入100萬元及以上，且資產(chǎn)總額2000萬元及以上的為小型企業(yè)；營業(yè)收入

43、100萬元以下或資產(chǎn)總額2000萬元以下的為微型企業(yè)。14）物業(yè)治理。從業(yè)人員1000人以下或營業(yè)收入5000萬元以下的為中小微型企業(yè)。其中，從業(yè)人員300人及以上，且營業(yè)收入1000萬元及以上的為中型企業(yè)；從業(yè)人員100人及以上，且營業(yè)收入500萬元及以上的為小型企業(yè)；從業(yè)人員100人以下或營業(yè)收入500萬元以下的為微型企業(yè)。15）租賃和商務(wù)服務(wù)業(yè)。從業(yè)人員300人以下或資產(chǎn)總額120000萬元以下的為中小微型企業(yè)。其中，從業(yè)人員100人及以上，且資產(chǎn)總額8000萬元及以上的為中型企業(yè)；從業(yè)人員10人及以上，且資產(chǎn)總額100萬元及以上的為小型企業(yè)；從業(yè)人員10人以下或資產(chǎn)總額100萬元以下的

44、為微型企業(yè)。16）其他未列明行業(yè)。從業(yè)人員300人以下的為中小微型企業(yè)。其中，從業(yè)人員100人及以上的為中型企業(yè)；從業(yè)人員10人及以上的為小型企業(yè)；從業(yè)人員10人以下的為微型企業(yè)。2.4.2 我國中小企業(yè)的特點1）企業(yè)組織結(jié)構(gòu)層次簡單中小企業(yè)的組織結(jié)構(gòu)層次專門少，部門分劃的也不是專門細，一樣要緊的治理差不多上由一個人到兩個人來進行，只有當那個決策者通過檢查之后才能進行生產(chǎn)，如此就降低了企業(yè)的生產(chǎn)效率。2）企業(yè)專門的生產(chǎn)運作模式隨著現(xiàn)代社會生產(chǎn)分工的細化,相當大部分的中小企業(yè)都作為大型企業(yè)的輔助性制造商。這就決定了中小企業(yè)對大企業(yè)的依存關(guān)系,而這種相互依存的關(guān)系又會阻礙中小企業(yè)內(nèi)部和外部供應(yīng)鏈網(wǎng)

45、絡(luò)的設(shè)計。在要緊的客戶級和企業(yè)級都需要搜尋清晰的供應(yīng)鏈指令,這將迫使中小企業(yè)的項目治理目標失去獨立性,需要按照大企業(yè)的生產(chǎn)變化進行適應(yīng)性調(diào)整或重新安排,因此中小企業(yè)中的采購、生產(chǎn)、銷售等運作特點同那些大企業(yè)相比有著明顯的不同。3）企業(yè)內(nèi)部治理人員職責模糊在中小企業(yè)中,各部門之間在職責上沒有清晰的界線。企業(yè)治理人員職責的模糊性,究其緣故在于中小企業(yè)的規(guī)模小、組織結(jié)構(gòu)簡單。一樣講來,企業(yè)的規(guī)模越大,其要求企業(yè)的組織結(jié)構(gòu)就越復(fù)雜,部門之間分工就越明確;而中小企業(yè)規(guī)模小,對應(yīng)地其組織結(jié)構(gòu)就顯得簡單,組織的正規(guī)化程度低,從而部門之間的分工就模糊。4）企業(yè)實際生產(chǎn)與打算推測的偏離較大實際生產(chǎn)與打算的偏離專

46、門明顯,要緊有兩種表現(xiàn)形式:實際生產(chǎn)的成品和生產(chǎn)的數(shù)量。隨著產(chǎn)品生命周期的縮短,大型企業(yè)持續(xù)地改進新的產(chǎn)品形式甚至向市場上頻繁推出全新產(chǎn)品。中小企業(yè)通常差不多上第三方輔助性制造商,它們的成品生產(chǎn)專門大程度上依靠于那些大企業(yè)要賣些什么產(chǎn)品。因此,關(guān)于中小企業(yè)來講,每年的打算和推測只能作為企業(yè)生產(chǎn)和銷售的一個粗略指導方針,而全然不能作為企業(yè)的實際生產(chǎn)打算12。2.4.3 中小企業(yè)生產(chǎn)調(diào)度的要緊咨詢題1）由于中小企業(yè)資金的不足，照成車間設(shè)備的先進程度不夠，同時設(shè)備的定期修理做的不夠好。車間設(shè)備的工作環(huán)境也不盡人意。2）由于沒有建立差不多的生產(chǎn)治理信息系統(tǒng)，因此生產(chǎn)信息零亂而分散。通常情形下，許多信息

47、對指揮下一個生產(chǎn)周期、下一天、甚至下一個小時的生產(chǎn)都專門重要。在手工處理方式下要靠調(diào)度對紙質(zhì)資料逐個查詢，現(xiàn)場查咨詢或測試、手工記錄并統(tǒng)計匯總，不僅工作量大，而且速度較慢，難以提升工作效率，且專門難實現(xiàn)加工車間與其他職能部門的信息。3）車間作業(yè)調(diào)度上，一樣是按照體會來安排零件的加工，由于設(shè)備數(shù)量少且分布較分散，因而極易造成設(shè)備負荷的不均衡與增加設(shè)備的閑暇時刻，同時，由于人為因素對生產(chǎn)阻礙較大，增加了生產(chǎn)的隨機性。導致不可預(yù)見的咨詢題隨時都可能發(fā)生。4）對零件的加工工時與設(shè)備利用情形無法進行定量分析，造成編制生產(chǎn)打算與進行生產(chǎn)調(diào)度決策的依據(jù)不足。導致對產(chǎn)品不能均衡成產(chǎn)。5）對許多與生產(chǎn)有關(guān)的數(shù)據(jù)

48、由于受工作量限制未予記錄，或記錄不完整、不規(guī)范，難以追查某些由于治理失誤而引起的責任事故。即便已記錄的數(shù)據(jù)在統(tǒng)計匯總中也難免發(fā)生錯誤，這些都難以滿足現(xiàn)代企業(yè)治理中用數(shù)字講話，實現(xiàn)科學治理的要求。6）調(diào)度工作缺乏預(yù)見性和預(yù)防性。在生產(chǎn)過程中，經(jīng)常會遇到一些突發(fā)性咨詢題，這要求調(diào)度人員及時調(diào)整作業(yè)打算；同時，調(diào)度工作要以防為主，必須幸免被動地抓缺件、堵漏洞的消極做法，而這些不借助于運算機,單獨依靠人工治理是難以實現(xiàn)的。第3章車間生產(chǎn)的調(diào)度方法研究調(diào)度咨詢題的研究方法通過五十多年的進展，經(jīng)歷了由簡單到復(fù)雜，從一元到多元的過程。從中也產(chǎn)生了許多算法，一樣的調(diào)度咨詢題差不多上關(guān)于具體生產(chǎn)環(huán)境中的復(fù)雜的、

49、多目標、動態(tài)的調(diào)度咨詢題的一種抽象和簡化，因而對一個調(diào)度算法能夠通過其如何表述這些復(fù)雜性進行分類。而能否適應(yīng)千差萬不的實際生產(chǎn)環(huán)境，能否取得令人中意的優(yōu)化成效，就成為了評估這一個調(diào)度算法的要緊標準。有關(guān)調(diào)度咨詢題的研究方法最初集中在數(shù)學規(guī)劃、系統(tǒng)仿真和簡單的規(guī)則上，這些方法不是調(diào)度結(jié)果不理想確實是難以解決復(fù)雜的實際調(diào)度咨詢題。隨著各種新的有關(guān)學科與優(yōu)化技術(shù)的建立和進展，在調(diào)度領(lǐng)域顯現(xiàn)了許多新的優(yōu)化方法，這些方法對解決車間調(diào)度咨詢題具有重要意義13。本文大體介紹了整數(shù)規(guī)劃法，啟發(fā)式方法，運算智能調(diào)度方法，這些方法己經(jīng)成為調(diào)度方法的主流。本文著重介紹了啟發(fā)式算法，并通過與其他算法的比較來講明啟發(fā)式

50、算法的優(yōu)缺點。3.1傳統(tǒng)的優(yōu)化理論與方法1）整數(shù)規(guī)劃法：通過對車間調(diào)度咨詢題建立一個整數(shù)規(guī)劃模型，采納基于枚舉思想的分支定界法、割平面法和0-1整數(shù)規(guī)劃法進行求解14。這類方法盡管從理論上能求得最優(yōu)解，但由于其運算復(fù)雜性，不能獲得實際應(yīng)用。2）多目標優(yōu)化法：多目標優(yōu)化方法是同時考慮不同目標的共同作用。關(guān)于給定的多個目標按各自的重要程度，分不乘以不同的權(quán)系數(shù)，然后相加得到目標函數(shù)，再對此目標函數(shù)在多目標的約束集合上求最優(yōu)解，也能夠選擇一個優(yōu)化目標作為要緊目標，而將其他目標作為約束處理，轉(zhuǎn)化為一個新約束條件下，求要緊的單目標最優(yōu)化咨詢題。多目標優(yōu)化能體現(xiàn)不同目標的重要程度，但它通常只能查找滿足約束

51、條件的中意解15。3）動態(tài)規(guī)劃法：由于車間生產(chǎn)過程的動態(tài)性，系統(tǒng)運行中任何約束條件的改變，都可能使原先求得的最優(yōu)解失效。利用動態(tài)規(guī)劃法，將車間生產(chǎn)調(diào)度過程按時刻劃分為若干個相互聯(lián)系的時期，列出各時期決策過程的函數(shù)方程，并利用動態(tài)規(guī)劃的最優(yōu)化原理進行求解，使整個過程的總成效達到最優(yōu)。動態(tài)規(guī)劃將求解咨詢題分解成多時期進行，使復(fù)雜咨詢題簡化，遞推求解過程中能夠利用實際應(yīng)驗，提升求解效率。然而動態(tài)變量必須滿足無后效性，使動態(tài)變量不僅依靠狀態(tài)轉(zhuǎn)移規(guī)律，還依靠于承諾決策集合和指標函數(shù)結(jié)構(gòu)，從而降低了它的通用性16。3.2啟發(fā)式方法啟發(fā)式方法因易于實現(xiàn)、運算復(fù)雜程度低等緣故，能夠用于動態(tài)實時調(diào)度系統(tǒng)中，一直

52、受到人們的關(guān)注，并開展了廣泛的研究。1）優(yōu)先調(diào)度規(guī)則：優(yōu)先規(guī)則是按時刻進程逐次為每臺設(shè)備安排一個加工對象時，按照某種規(guī)則，從候選的等待作業(yè)中選取優(yōu)先級最高的作業(yè)安排加工的方法。優(yōu)先規(guī)則可按照不同的優(yōu)化目標制定，不受零件數(shù)、工序數(shù)與工藝路線的限制，因此應(yīng)用也比較廣泛。常見的簡單規(guī)則與組合優(yōu)先規(guī)則分不見表3-1與表3-2:表3-1常見的簡單優(yōu)先級規(guī)則在舁廳P規(guī)則名稱1EDD交貨期最早2FCFS先進先出3LCFS后進先出4JP工件優(yōu)先值5LWKR剩余加工量最小6MWKR剩余加工量最大7FOPNR剩余工序數(shù)最少8MOPNR剩余工序數(shù)最多9SPT加工時刻最短10LPT加工時刻最長11SLACK最小放松量

53、12NINR下工序等待作業(yè)數(shù)最少13WINQ下工序等待作業(yè)加工量最小14RANDOM隨機其中零件放松量-交貨期-當前時刻-剩余加工時刻，當零件放松量為負時，表明其不能按期交貨。優(yōu)先權(quán)規(guī)則是設(shè)定每一零件、設(shè)備的優(yōu)先等級，優(yōu)先響應(yīng)優(yōu)先級高的申請對象17。啟發(fā)式規(guī)則，如LookAhead規(guī)則要緊研究當用簡單規(guī)則選擇作用時，所選作業(yè)在處理過程中對另一作業(yè)的阻礙?？赡苁茏璧K的作業(yè)是到達隊列等待服務(wù)的作業(yè)。LookAhead規(guī)則承諾在某一加工設(shè)備閑暇時刻插入一個加工時刻不大于某值的零件加工，其動態(tài)性較好。SPT是應(yīng)用最廣泛的一種調(diào)度規(guī)則，它對所有基于零件完工時刻的指標都有較好的成效，如平均生產(chǎn)周期、平均延

54、遲時刻、設(shè)備負荷率等。旨在降低車間在制品占用量為目標的作業(yè)排序一樣都用SPT。具缺點是對公序時刻長的作業(yè)，越長越往后排，容易造成加工量大的作業(yè)產(chǎn)生延誤，而加工量大的作業(yè)往往是生產(chǎn)中的關(guān)鍵零件，因而對生產(chǎn)打算的完成產(chǎn)生加大阻礙。LPT與SPT相反，優(yōu)先考慮加工時刻長的零件，但又明顯地增加了零件在生產(chǎn)中的平均等待時刻，及增大了生產(chǎn)中在制品占用量。MWKR是考慮剩余加工量大的作業(yè)容易延遲固優(yōu)先安排。關(guān)于要成套地投入裝配的零件，能夠有效地縮短零件組的總生產(chǎn)周期。LWKR則是使加工進度快的零件加速完成。MOPNR是優(yōu)先安排剩余工序數(shù)最多的作業(yè)，與MWKR相似，目標是縮短零件組的生產(chǎn)周期。所不同的是他考慮

55、了工序間轉(zhuǎn)移和等待時刻，這部分時刻往往比加工時刻長得多。MOPNR與MWKR相似，其目標也是減少車間內(nèi)的在制品量。SLACK是促使打算能按期完工的一種重要的優(yōu)先級規(guī)則。由于考慮到交貨期與當前時刻的關(guān)系，在于交貨期有關(guān)的方面表現(xiàn)出優(yōu)越性，如平均延遲、滿足交貨期的零件比例等。FIFO對減少零件平均通過時刻是較優(yōu)的，常用于flow-shop型的加工車間。NINR、WINQ與前述的規(guī)則不同，它考慮的不僅是當前等待作業(yè)集合的狀況，而且要推測下工序等待作業(yè)集合中零件的狀況。原則上是不選取那些在下工序因等待集合中作業(yè)擁擠而受阻的作業(yè)，而是優(yōu)先選取能順利投入加工的作業(yè)。其目標是加快生產(chǎn)進度，縮短零件的平均生產(chǎn)周期。在多數(shù)情形下，使用符合規(guī)則比使用簡單規(guī)則會取得更好的成效。如以SPT為第一規(guī)則，再以固定間隔檢查隊列，用FCFS使等待過久的零件出隊加工，會使作業(yè)完成時刻與提早/延遲指標都達到理想成效。表3-2常見的組合優(yōu)先級規(guī)則在舁廳P規(guī)則名稱含義1SPTATOT最短加工時刻與總加工時刻的乘積最大2SPT/TOT最短加工時刻與總加工時刻之比最大3SLACK/FOPNR放松時刻與剩余工序數(shù)之比最大4SLACK/LWKR放松時刻與剩余加工量之比最大以上這些優(yōu)先調(diào)度規(guī)則的簡