典型車間調(diào)度問題的分析與研究

典型車間調(diào)度問題的分析與研究Abstract：Thispaperstudiestwotypicalproblemsinthecurrentjobshopschedulingproblem,namely,theflowshopschedulingproblemandthejobshopschedulingproblem,inwhichthebasicprinciplesandresearchmethodsoftheflowshopschedulingproblemaredescribedindetail.Thebasicprinciples,schedulingstrategiesandresearchmethodsofthejobshopschedulingproblemareanalyzedandsummarized.Throughthediscussionofthispaper,itprovidesausefulreferenceforfurtherexpandingthein-depthstudyofthesetwotypicaljobshopschedulingproblems.Keywords:flowshopscheduling;jobshopscheduling;schedulingstrategy;schedulingmethod1概述率間調(diào)度問題指的是如何在有限的資源環(huán)境里，通過合理安排車間生產(chǎn)任務(wù)，進(jìn)而滿足一至多個(gè)性能指標(biāo)的過程。隨著經(jīng)濟(jì)社會(huì)的不斷發(fā)展，企業(yè)之間的競(jìng)爭也愈發(fā)激烈，生產(chǎn)車間的生產(chǎn)規(guī)模也越來越大，如何合理安排車間調(diào)度也越來越復(fù)朵，車間調(diào)度業(yè)已成為智能制造的基礎(chǔ)組成部分。對(duì)于車間調(diào)度的優(yōu)化問題研究己經(jīng)成為工業(yè)發(fā)展的重點(diǎn)研究問題之一，對(duì)車間調(diào)度進(jìn)行優(yōu)化是提升現(xiàn)代制造技術(shù)和企業(yè)管理水平的重要內(nèi)容。開展車間調(diào)度研究，尋求良好的生產(chǎn)車間調(diào)度問題求解方案具有十分巨大的理論價(jià)值和實(shí)際應(yīng)用價(jià)值。本文針對(duì)兩種典型的生產(chǎn)車間調(diào)度問題，就基木原理、研究方法等展開探討與分析。2流水車間調(diào)度流水車間調(diào)度問題是加工制造業(yè)中的一類重要的規(guī)劃問題，多數(shù)情況下研究流水車間調(diào)度問題的加工任務(wù)中的作業(yè)個(gè)數(shù)都要大于3,這時(shí)候的車間調(diào)度問題是NP-hard問題。在過去的幾十年里國內(nèi)外學(xué)者對(duì)這個(gè)問題做了大量的研究，相應(yīng)的提出了許多解決這一問題的方法。這些方法大致可分成精確算法、啟發(fā)式算法和元啟發(fā)式算法三種。由于NPhard問題的復(fù)雜性，所以，精確算法無法對(duì)規(guī)模較大的問題進(jìn)行求解，只能解決一些規(guī)模較小的流水車間調(diào)度問題。啟發(fā)式算法的優(yōu)點(diǎn)是能夠快速構(gòu)造問題的解，但是通常得到的這些解的質(zhì)量較差，無法滿足要求。元啟發(fā)式算法能夠在較短的時(shí)間里而得到較高質(zhì)量的解，所以，廣泛采用這種算法來對(duì)流水車間調(diào)度問題進(jìn)行求解。流水車間調(diào)度的主要特點(diǎn)流水車間調(diào)度問題的主要特點(diǎn)是一個(gè)生產(chǎn)任務(wù)內(nèi)包含一些代加工的作業(yè)，這些作業(yè)在處理機(jī)上的加工順序都相同，因此也被稱為同順序調(diào)度問題。流水車間調(diào)度問題的基木思路為：將一個(gè)加工任務(wù)中所有的待加工作業(yè)合理的安排到加工企業(yè)內(nèi)的處理機(jī)上，使得整個(gè)加工過程的某一項(xiàng)或者某幾項(xiàng)指標(biāo)達(dá)到最優(yōu)的目的。其中，每個(gè)作業(yè)在處理機(jī)上的準(zhǔn)備時(shí)間和加工時(shí)間、每個(gè)作業(yè)的交貨期等都是己知的,且要求每臺(tái)處理機(jī)上加工工件的順序相同。在某一時(shí)段內(nèi)每臺(tái)處理機(jī)只能對(duì)一個(gè)工件進(jìn)行操作，操作過程不能中斷直到作業(yè)的這一個(gè)操作完成為止。從對(duì)流水車間調(diào)度的描述可以看出它是許多實(shí)際流水線生產(chǎn)調(diào)度問題的簡化模型，是目前研究最廣泛的一類典型調(diào)度問題，受到了許多研究學(xué)者的重視，且提出了許多針對(duì)該問題的求解方法。但是主要的研究還是集中在單目標(biāo)的流水車間調(diào)度問題上，而在實(shí)際生產(chǎn)環(huán)境中，流水車間調(diào)度問題存在著多個(gè)相互沖突的目標(biāo)需要進(jìn)行優(yōu)化，因此開展多目標(biāo)流水車間調(diào)度問題的研究更加符合實(shí)際?；旌狭魉囬g調(diào)度混合流水車間調(diào)度是一種相對(duì)比較復(fù)雜的流水車間調(diào)度。它是根據(jù)石油工業(yè)的背景提出來的。在被提出后的幾十年里，許多研究學(xué)者對(duì)這一類問題進(jìn)行了研究，得到了許多解決這一問題的方法?；旌狭魉囬g調(diào)度問題就其木質(zhì)而言，可以分為兩類經(jīng)典調(diào)度問題：標(biāo)準(zhǔn)的流水車間調(diào)度問題和并行機(jī)調(diào)度問題。它的主要特征是：待加工作業(yè)的某些操作可以在幾臺(tái)并行處理機(jī)上進(jìn)行加工，因此混合流水車間調(diào)度也被稱為多機(jī)多階段流水車間調(diào)度問題?；旌狭魉囬g調(diào)度問題經(jīng)常出現(xiàn)在柔性流水線的流程工業(yè)中，所以它也被稱為柔性流水車間調(diào)度問題，其研究目的即對(duì)工序進(jìn)行有效的排序，使得所選擇的某個(gè)性能指標(biāo)達(dá)到最優(yōu)，進(jìn)而實(shí)現(xiàn)企業(yè)效益最優(yōu)。由于其在理論研究領(lǐng)域的代表性和在諸多工業(yè)領(lǐng)域的廣泛應(yīng)用背景，近年來得到許多研究者的重視。混合流水車間調(diào)度的特點(diǎn)為多目標(biāo)性、多約束性、多階段性以及非線性。其本質(zhì)是由一系列加工過程組成，加工過程中的某些階段可能只有一臺(tái)處理機(jī)，但在整個(gè)加工過程中至少存在一個(gè)階段有兩臺(tái)或者兩臺(tái)以上的并行處理機(jī)可以對(duì)其進(jìn)行加工。待加工的工件可由并行處理機(jī)中的任一臺(tái)進(jìn)行加工，工件在車間里必須是單向流動(dòng)的?；旌狭魉囬g調(diào)度在流程加工制造行業(yè)中應(yīng)用比較廣泛，如鋼鐵企業(yè)加工工藝大概可以分為煉鋼、連鑄和熱軋三個(gè)階段，每個(gè)階段都會(huì)存在多個(gè)并行處理機(jī)可以對(duì)其進(jìn)行操作。3作業(yè)車間調(diào)度作業(yè)車間調(diào)度問題是計(jì)算機(jī)集成加工制造領(lǐng)域的一個(gè)重要組成部分，是最經(jīng)典的離散制造系統(tǒng)調(diào)度問題，從數(shù)學(xué)規(guī)劃的角度來看又是一類困難的組合優(yōu)化問題。由于作業(yè)車間調(diào)度是源于制造業(yè)生產(chǎn)的實(shí)際需要，所以近年來作業(yè)車間調(diào)度成為一個(gè)研究熱點(diǎn)。作業(yè)車間調(diào)度問題的基本思路為：將一個(gè)加工任務(wù)中所有的待加工作業(yè)合理的安排到加工企業(yè)內(nèi)的處理機(jī)上，使得整個(gè)加工過程的某一項(xiàng)或者某幾項(xiàng)指標(biāo)達(dá)到最優(yōu)的目的。要求每個(gè)作業(yè)的操作都需要占用處理機(jī)或其它資源才能完成加工過程，在這個(gè)過程中必須滿足各個(gè)作業(yè)的工藝路線、工藝次序要求進(jìn)行加工。在加工過程中每臺(tái)處理機(jī)可以加工作業(yè)的若干操作，并且在不同處理機(jī)上能加工的操作集可以是不同的，這是作業(yè)車間調(diào)度與流水車間作業(yè)調(diào)度最大的不同，因而使作業(yè)車間調(diào)度更加復(fù)雜。簡而言之，作業(yè)車間調(diào)度的本質(zhì)是確定一個(gè)滿足各種約束的調(diào)度，該調(diào)度能在某個(gè)特定的時(shí)間段將每個(gè)工序分配到對(duì)應(yīng)的處理機(jī)上，然后找到可以最小化加工成本和時(shí)間等某幾個(gè)性能的調(diào)度。作業(yè)車間調(diào)度的策略基于作業(yè)車間調(diào)度問題的復(fù)雜性，根據(jù)具體情況選擇相應(yīng)的解決方案，為了能夠得到更好的調(diào)度，可以從策略上對(duì)作業(yè)車間調(diào)度進(jìn)行研究。目前形成的策略主要有以下幾種：（2）并行和分布策略：從車間調(diào)度的描述就可以看出它是一個(gè)比較復(fù)雜的問題，所以求解大規(guī)模的作業(yè)車間調(diào)度問題來說是一件是非常困難的事情?；诖嗽S多的研究學(xué)者提出用并行或分解的策略來解決車間調(diào)度問題。這種策略主要應(yīng)用在不同車間控制結(jié)構(gòu)和高度問題等復(fù)雜性的作業(yè)車間調(diào)度問題。（2）分解和成組策略：利用分解生產(chǎn)計(jì)劃的策略，可以降低作業(yè)車間調(diào)度計(jì)算的復(fù)雜性和規(guī)模，經(jīng)過分解后的作業(yè)調(diào)度問題更加容易得到好的解，同時(shí)還可以優(yōu)化系統(tǒng)的一些性能指標(biāo)。這種方法在制造系統(tǒng)應(yīng)用的比較廣泛?；舅枷胧歉鶕?jù)工件和機(jī)器之間的相似性對(duì)它們進(jìn)行分類，然后利用組內(nèi)的相似性來提高工作效率。（3）多目標(biāo)權(quán)衡調(diào)度策略：在實(shí)際生產(chǎn)過程中，以多目標(biāo)的作業(yè)車間調(diào)度問題為主。如最大化生產(chǎn)效率、最小化生產(chǎn)周期、最小化加工成木等等，其中有些目標(biāo)還是相互影響、相互沖突的，所以要對(duì)多目標(biāo)進(jìn)行權(quán)衡分析,得到一個(gè)均衡的調(diào)度。（4）生產(chǎn)計(jì)劃與調(diào)度集成策略：應(yīng)用這種策略可以對(duì)作業(yè)車間調(diào)度的全局優(yōu)化和生產(chǎn)系統(tǒng)的柔性進(jìn)行提升，所以生產(chǎn)計(jì)劃與調(diào)度集成策略符合先進(jìn)制造模式的思路。（5）人機(jī)交互策略:由于作業(yè)車間調(diào)度問題的多目標(biāo)性和各種因素的影響，為了能夠得到好的調(diào)度結(jié)果，往往需要與調(diào)度決策者的經(jīng)驗(yàn)知識(shí)相結(jié)合來尋找最優(yōu)的調(diào)度。人機(jī)交互的策略可以減少系統(tǒng)的搜索空間，能夠更好更快的找到復(fù)雜的作業(yè)車間調(diào)度問題的最優(yōu)解。作業(yè)車間調(diào)度的研究方法作業(yè)車間調(diào)度是生產(chǎn)調(diào)度問題中的典型代表，很多領(lǐng)域中具體的組合優(yōu)化問題都可以抽象為作業(yè)車間調(diào)度問題進(jìn)行求解。所以各領(lǐng)域的研究學(xué)者對(duì)作業(yè)車間調(diào)度問題進(jìn)行了深入而廣泛的研究，并應(yīng)用到各自的領(lǐng)域當(dāng)中，取得了令人滿意的結(jié)果。特別是機(jī)械、自動(dòng)化、計(jì)算機(jī)和數(shù)學(xué)等不同領(lǐng)域的結(jié)合交叉，為解決作業(yè)車間調(diào)度問題提出了眾多新的研究理論和新的研究方法。這些方法主要有三種類型：精確算法、近似算法以及智能搜索算法：（1）精確算法：這類方法雖然從理論上能夠?qū)ふ业阶顑?yōu)解，但由于計(jì)算復(fù)雜度較高的一些原因，使得精確求解方法只適用于規(guī)模不大的問題和性質(zhì)并不十分復(fù)雜的優(yōu)化問題。而在實(shí)際生產(chǎn)環(huán)境中存在許多不確定性的因素會(huì)對(duì)問題的求解帶來很大的困難，所以很難應(yīng)用精確方法去處理實(shí)際調(diào)度問題。（2）近似算法：由于大多數(shù)的作業(yè)車間調(diào)度問題屬于NP-hard問題。精確求解方法無法解決一些計(jì)算量大的復(fù)雜問題，所以許多研究學(xué)者研究這一問題采用各種近似或者啟發(fā)式的方法來對(duì)問題進(jìn)行求解。近似求解方法能在有限的時(shí)間內(nèi)找到相對(duì)滿意的次優(yōu)解，這種方法可以用來解決較大規(guī)模的實(shí)際調(diào)度問題。（3）智能搜索算法：這種方法是根據(jù)生物種群特有的一些屬性而抽象出來的一類算法。這類方法的特點(diǎn)是通用性強(qiáng)、求解的速度快且無需問題的任何特殊信息等。這種算法雖也是近似方法，但他們可以找到解空間中的最優(yōu)