亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        多產(chǎn)品批處理的多機(jī)并行調(diào)度問題研究

        2015-12-20 08:45:40馮夢華FENGMenghuaXIEYong
        物流科技 2015年6期
        關(guān)鍵詞:懲罰遺傳算法訂單

        馮夢華,謝 勇 FENG Meng-hua, XIE Yong

        (華中科技大學(xué) 系統(tǒng)工程研究所,湖北 武漢430074)

        (Institute of Systems Engineering, Huazhong University of Science & Technology, Wuhan 430074, China)

        0 引 言

        生產(chǎn)計(jì)劃與調(diào)度問題是制造企業(yè)最基礎(chǔ)也最核心的問題,是在滿足某些約束條件(如有限生產(chǎn)能力及資源、任務(wù)釋放時(shí)間和截止期等) 下對任務(wù)進(jìn)行合理排序,并安排各個(gè)任務(wù)開工時(shí)間,最終實(shí)現(xiàn)企業(yè)一個(gè)或多個(gè)目標(biāo)的最優(yōu)化。實(shí)際中對調(diào)度的評價(jià)大致可歸為三類:最大能力指標(biāo)、成本指標(biāo)、客戶滿意度指標(biāo)[1],其中最大能力指標(biāo)大多應(yīng)用在需求固定或需求無上限的情況下,傳統(tǒng)生產(chǎn)調(diào)度應(yīng)用較多,但實(shí)際卻是提前完成生產(chǎn)的成品需入成品倉庫需要支付一筆不小的倉儲費(fèi)用,延期生產(chǎn)產(chǎn)品則會有損企業(yè)聲譽(yù),同時(shí)企業(yè)還需支付違約金,因此實(shí)際中更多的綜合考慮庫存成本以及延期懲罰費(fèi)用。

        考慮庫存成本、延期懲罰生產(chǎn)調(diào)度問題的核心是準(zhǔn)時(shí)化生產(chǎn)。專家學(xué)者對其進(jìn)行大量研究:Held[2]和Bagchi U[3]研究了單機(jī)環(huán)境下的提前、拖期調(diào)度問題;Prabuddha De[4]探討了單機(jī)調(diào)度完成時(shí)間偏差最小化問題,調(diào)度中考慮了不同任務(wù)的加權(quán)系數(shù)情況;Coleman[5]針對考慮任務(wù)準(zhǔn)備時(shí)間與加工順序相關(guān)這一實(shí)際情況研究單機(jī)調(diào)度問題;Fry and Armstrong[6],Garey and Tarjan[7]和Yano and Kim[8]研究了給定排序下的開工時(shí)間優(yōu)化問題,但對懲罰權(quán)重有一定的限制;Cheng T C E[9]討論了互不相關(guān)的任務(wù)在多機(jī)的并行調(diào)度問題,闡述流程時(shí)間加成本最小、提前拖期懲罰費(fèi)用最小兩個(gè)問題。

        多機(jī)并行調(diào)度問題雖得到一定研究,但調(diào)度的任務(wù)間大多是無關(guān)的,然實(shí)際中會由于生產(chǎn)容量限制需要將訂單拆分為加工任務(wù),這些任務(wù)間實(shí)際上存在一定關(guān)系的,這對調(diào)度有一定的影響。本文以某酒企業(yè)生產(chǎn)為研究背景,研究已知交貨期的訂單在生產(chǎn)容量限制分割為子訂單后的多機(jī)并行調(diào)度問題,盡量實(shí)現(xiàn)各訂單的準(zhǔn)時(shí)化生產(chǎn)。

        1 問題描述

        本文研究的酒生產(chǎn)調(diào)度是在一般車間調(diào)度問題上簡化的,不考慮具體的工藝路線,整套的工藝路線在一臺機(jī)器上即可生產(chǎn)完;其中加入了生產(chǎn)中容量限制這一約束,在可能情況下都以最大容量組織生產(chǎn),最后不夠最大容量的人任為一批組織生產(chǎn),這就要求先要對生產(chǎn)訂單進(jìn)行分割,在此基礎(chǔ)上進(jìn)行調(diào)度。本文的計(jì)劃排程描述如下:實(shí)現(xiàn)i個(gè)訂單在m臺機(jī)器上并行調(diào)度,其中涉及訂單拆分情況。排產(chǎn)調(diào)度要做的是:(1) 根據(jù)產(chǎn)品的最大生產(chǎn)容量將i個(gè)訂單分割為各子訂單即要排產(chǎn)的任務(wù)。(2) 把各子訂單安排到m臺機(jī)器上生產(chǎn)并確定產(chǎn)線上子訂單的生產(chǎn)順序和生產(chǎn)時(shí)間;調(diào)度的目標(biāo)是使得所有訂單能夠在交貨

        期附近結(jié)束生產(chǎn),使得批生產(chǎn)、庫存成本、延期懲罰費(fèi)用最小。生產(chǎn)計(jì)劃流程圖如圖1 所示:

        2 數(shù)學(xué)模型

        對多產(chǎn)品批處理的多機(jī)并行調(diào)度問題作如下假設(shè):

        (1) 每個(gè)訂單只包含一種產(chǎn)品,并指定交貨期、生產(chǎn)數(shù)量;

        (2) 每種產(chǎn)品可以在多臺機(jī)器上生產(chǎn);

        (3) 生產(chǎn)中不允許出現(xiàn)中斷;

        (4) 每一次生產(chǎn)都以最大容量生產(chǎn),不夠最大容量仍組織一次生產(chǎn);

        (5) 產(chǎn)品在機(jī)器上的批處理時(shí)間依產(chǎn)品種類不同;

        (6) 產(chǎn)品之間的轉(zhuǎn)換時(shí)間依產(chǎn)品種類不同,不同產(chǎn)線上相同轉(zhuǎn)換順序的轉(zhuǎn)換時(shí)間相同。

        該模型中使用的符號索引、決策變量及參數(shù)如表1 所示:

        表1 變量參數(shù)定義

        問題的數(shù)學(xué)模型為:

        式(1) 是計(jì)劃排產(chǎn)的目標(biāo),表達(dá)式中依次為批生產(chǎn)費(fèi)用、延期懲罰費(fèi)用、生產(chǎn)庫存懲罰,其中庫存費(fèi)用與單位庫存成本及庫存時(shí)間成正比,而延期費(fèi)用與訂單的生產(chǎn)數(shù)量成正比。表達(dá)式中的完成時(shí)間Cik與決策變量關(guān)系為式(2)表示分割后的每個(gè)子訂單智能安排在一條產(chǎn)線上約束;式(3) 表示任務(wù)間加工順序約束,前驅(qū)任務(wù)完工后才能開始后繼任務(wù);式(4) 表示訂單的分割子訂單的開始時(shí)間與完成時(shí)間之間的約束關(guān)系。

        3 遺傳算法優(yōu)化求解

        本文調(diào)度借鑒一般調(diào)度問題的解決工具遺傳算法,利用遺傳算法能同時(shí)使用多個(gè)搜索點(diǎn),有能力在各種調(diào)度方案之間進(jìn)行選擇交叉和變異等運(yùn)算,可以跳出局部最優(yōu)的陷阱,使解集性能不斷得到優(yōu)化。但本文求解過程不似一般調(diào)度問題,存在區(qū)別為:調(diào)度任務(wù)間不是相互獨(dú)立的。一般調(diào)度問題中各任務(wù)間相互獨(dú)立,在使用遺傳算法確定其生產(chǎn)順序后,采用線性規(guī)劃方法即可求解;但本文中調(diào)度任務(wù)間并不完全獨(dú)立,存在多個(gè)任務(wù)來自同一訂單情況,而目標(biāo)函數(shù)中庫存、延期懲罰分別與任務(wù)以及訂單相關(guān),兩者之間有關(guān)聯(lián),采用線性規(guī)劃問題不能得以解決,故在采用遺傳算法優(yōu)化任務(wù)的排序順序后嵌套遺傳算法確定優(yōu)化排產(chǎn)順序下的各任務(wù)開始生產(chǎn)時(shí)間使得生產(chǎn)、庫存、延期懲罰費(fèi)用最小。其算法流程如圖2 所示。

        (1) 個(gè)體編碼

        外層遺傳算法求解任務(wù)的機(jī)臺號及其順序,采用向量組的編碼方法,任務(wù)k在產(chǎn)線m上加工,則位基因表示為個(gè)體基因則為其中第一行為隨機(jī)排列的任務(wù),第二行為任務(wù)的產(chǎn)線編號,任務(wù)間的加工順序則遵循在基因第一行中的排列順序。

        內(nèi)層遺傳算法求解各任務(wù)開始加工時(shí)間,采用一般向量編碼方法,任務(wù)單k開始加工的時(shí)間Sk,則個(gè)體基因?yàn)?/p>

        (2) 適應(yīng)度函數(shù)的選取

        (3) 選 擇

        兩層遺傳算法均選取最優(yōu)保存策略為選擇機(jī)制,保證適應(yīng)性好的個(gè)體保留到下一代中。

        (4) 交 叉

        外層遺傳算法中向量組基因若采用傳統(tǒng)的交叉方法,可能會產(chǎn)生任務(wù)加工產(chǎn)線不滿足約束條件的不合法個(gè)體,基于此外層采用EOX 交叉法:在交叉操作的兩父代個(gè)體(A、B) 中選擇父代個(gè)體(A),隨機(jī)取其中的一段基因串(S),將B中的第一行元素與S的第一行元素進(jìn)行比較,如果存在相同的則從B中刪除掉對應(yīng)元素的基因,將S插入到B中被刪除掉的基因第一行元素中與S中第一行第一個(gè)元素相同的地方,形成新的個(gè)體。依上述交叉過程反過來即可產(chǎn)生另一新個(gè)體。

        內(nèi)層遺傳算法中的位基因涉及浮點(diǎn)數(shù),采用中間交叉即子個(gè)體i=父個(gè)體Ai+F× (父個(gè)體Bi-父個(gè)體Ai),直至交叉產(chǎn)生滿足時(shí)間約束關(guān)系的個(gè)體。

        (5) 變 異

        外層算法中的個(gè)體基因包含任務(wù)加工產(chǎn)線及其順序,變異時(shí)要考慮任務(wù)加工產(chǎn)線以及任務(wù)加工順序變異,采用單點(diǎn)變異(改變?nèi)蝿?wù)的加工產(chǎn)線) 及交換變異(改變?nèi)蝿?wù)的加工順序) 相結(jié)合的方法保證變異的多樣性。

        內(nèi)層算法中根據(jù)任務(wù)的加工順序計(jì)算其開始加工時(shí)間范圍,在此范圍內(nèi)對開始加工時(shí)間變異。

        (6) 終止條件

        設(shè)定循環(huán)最大次數(shù)。

        4 實(shí)驗(yàn)結(jié)果分析比較

        上述數(shù)學(xué)模型中目標(biāo)函數(shù)考慮了庫存、拖期懲罰以及生產(chǎn)啟動三種費(fèi)用,將該模型與目標(biāo)中只考慮其中一項(xiàng)比較,研究不同費(fèi)用目標(biāo)對調(diào)度結(jié)果以及各項(xiàng)性能指標(biāo)改變,本文主要考慮目標(biāo)中只有拖期懲罰費(fèi)用。為了方便,簡記兩種模型目標(biāo)為:考慮三種費(fèi)用記為費(fèi)用和模型,只考慮拖期懲罰記為拖期模型。

        采用Balakrishnan N[10]中參數(shù)設(shè)置規(guī)則設(shè)置實(shí)驗(yàn)數(shù)據(jù):生產(chǎn)啟動費(fèi)用滿足U[0,5 0 ];產(chǎn)品間的轉(zhuǎn)換時(shí)間滿足U[25,75 ];產(chǎn)品生產(chǎn)批量及批處理時(shí)間均滿足N(100,100);產(chǎn)品的庫存成本及拖期懲罰滿足U[0,4]、U[0,6];訂單中產(chǎn)品生產(chǎn)數(shù)量滿足U[0,N],其中N=批次容量*產(chǎn)線數(shù);訂單截止期則滿足U[1.2*processtime,3*processtime],其中processtime是產(chǎn)品的批處理時(shí)間。

        參數(shù)設(shè)置完后,比較不同模型中三種費(fèi)用及各項(xiàng)性能指標(biāo),然后改變拖期懲罰系數(shù)進(jìn)行相同實(shí)驗(yàn)。不同模型的三種費(fèi)用結(jié)果如表2、表3 所示:

        表2 拖期模型的各項(xiàng)費(fèi)用數(shù)據(jù)

        表3 費(fèi)用和模型的各項(xiàng)費(fèi)用數(shù)據(jù)

        不同模型的各項(xiàng)性能指標(biāo)結(jié)果如表4、表5 所示。

        表4 拖期模型的各項(xiàng)性能指標(biāo)

        表5 費(fèi)用和模型的各項(xiàng)性能指標(biāo)

        通過表4、表5 的數(shù)據(jù)對比可知,相同懲罰系數(shù)下拖期模型的延遲訂單數(shù)小于費(fèi)用和模型,訂單最大完成時(shí)間、最大拖期時(shí)間均小但是最大在庫時(shí)間大,因?yàn)橥掀谀P椭豢紤]拖期費(fèi)用要求訂單盡量不延期,任務(wù)調(diào)度時(shí)任務(wù)間的時(shí)間間隙會減小,相應(yīng)訂單延遲數(shù)、最大完成時(shí)間、最大拖期時(shí)間均小,但會形成大量成品的在庫積壓,犧牲在制品庫存積壓縮減訂單延期;且隨著懲罰系數(shù)增大,延遲訂單數(shù)、最大完成時(shí)間、最大拖期時(shí)間減小、最大庫存時(shí)間增大,因?yàn)殡S著懲罰系數(shù)增大,懲罰費(fèi)用在總費(fèi)用中占的比例逐漸增大,這要求排產(chǎn)時(shí)訂單不延期,任務(wù)間的時(shí)隙會漸漸變小直至為0,成品的在庫時(shí)間也會增大。特別說明,表3 中延遲訂單數(shù)并沒有明顯變化因?yàn)橛唵瘟縉=6 情況下各訂單間截止日期比較相近,在最小化拖期懲罰下排產(chǎn)會造成較多的訂單延遲且變化不大;表4 中延遲訂單數(shù)變化比較明顯因?yàn)橛唵蜰=9 情況下訂單間截止期有比較大的差距,隨著懲罰系數(shù)增大,提前生產(chǎn)的訂單數(shù)量會增大延遲的訂單數(shù)就會逐漸減少。

        不同訂單量,不同拖期懲罰系數(shù)下各費(fèi)用如圖3、圖4 所示。

        由圖3、圖4 可知,不同懲罰系數(shù)下,拖期模型的拖期懲罰費(fèi)用小于費(fèi)用和模型,但是庫存費(fèi)用、總費(fèi)用均大,因?yàn)橥掀谀P椭豢紤]拖期費(fèi)用要求訂單盡量不延期但是允許提前生產(chǎn)存在,對比下會造成更多的庫存費(fèi)用,拖期模型是通過增大庫存費(fèi)用來減少懲罰費(fèi)用,又由于懲罰費(fèi)用小時(shí)庫存費(fèi)用在總費(fèi)用占有較大比例會造成最終總費(fèi)用增大;且隨著懲罰系數(shù)的增大,不同目標(biāo)下費(fèi)用之間的差距減小,因?yàn)殡S著懲罰系數(shù)的增大,懲罰費(fèi)用在總費(fèi)用中占的比例逐漸增大。相比只考慮拖期費(fèi)用,準(zhǔn)時(shí)化生產(chǎn)的費(fèi)用和模型為企業(yè)提供良好的選擇。

        5 結(jié)束語

        針對多產(chǎn)品生產(chǎn)調(diào)度問題,結(jié)合準(zhǔn)時(shí)化生產(chǎn)理念,提出了一種混合整數(shù)數(shù)學(xué)模型,模型中考慮批量生產(chǎn)約束、生產(chǎn)啟動時(shí)間以及多機(jī)并行等實(shí)際問題。比較不同拖期懲罰系數(shù)及不同目標(biāo)下的各項(xiàng)性能指標(biāo)。通過實(shí)驗(yàn)對比數(shù)據(jù),考慮提前/拖期懲罰費(fèi)用、生產(chǎn)啟動費(fèi)用之和優(yōu)于只考慮拖期懲罰,從利潤角度出發(fā)為企業(yè)提供一個(gè)良好的解決方案,且為不同指標(biāo)需求提供選擇。進(jìn)一步的研究可考慮結(jié)合啟發(fā)式規(guī)則排產(chǎn)縮短計(jì)算時(shí)間。

        [1] 宋毅. 基于遺傳算法的生產(chǎn)調(diào)度方法及其軟件實(shí)現(xiàn)[D]. 杭州:浙江工業(yè)大學(xué)(碩士學(xué)位論文),2003.

        [2] Held M, Karp R M. A dynamic programming approach to sequencing problems[J]. Journal of the Society for Industrial &Applied Mathematics, 1962,10(1):196-210.

        [3] Bagchi U, Sullivan R S, Chang Y L. Minimizing mean squared deviation of completion times about a common due date[J].Management Science, 1987,33(7):894-906.

        [4] De P, Ghosh J B, Wells C E. Scheduling to minimize weighted earliness and tardiness about a common due-date[J]. Computers & operations research, 1991,18(5):465-475.

        [5] COLEMAN B. TECHNICAL NOTE: A SIMPLE MODEL FOR OPTIMIZING THE SINGLE MACHINE EARLY/TARDY PROBLEM WITH SEQUENCE-DEPENDENT SETUPS[J]. Production and Operations Management, 1992,1(2):225-228.

        [6] Fry T D, Armstrong R D, Blackstone J H. Minimizing weighted absolute deviation in single machine scheduling[J]. IIE transactions, 1987,19(4):445-450.

        [7] Garey M R, Tarjan R E, Wilfong G T. One-processor scheduling with symmetric earliness and tardiness penalties[J]. Mathematics of Operations Research, 1988,13(2):330-348.

        [8] Yano C A, Kim Y D. Algorithms for a class of single-machine weighted tardiness and earliness problems[J]. European Journal of Operational Research, 1991,52(2):167-178.

        [9] Cheng T C E, Chen Z L. Parallel-machine scheduling problems with earliness and tardiness penalties[J]. Journal of the Operational Research Society, 1994(5):685-695.

        [10] Balakrishnan N, Kanet J J, Sridharan V. Early/tardy scheduling with sequence dependent setups on uniform parallel machines[J]. Computers and Operations Research, 1999,26(2):127-141.

        猜你喜歡
        懲罰遺傳算法訂單
        春節(jié)期間“訂單蔬菜”走俏
        新產(chǎn)品訂單紛至沓來
        神的懲罰
        小讀者(2020年2期)2020-03-12 10:34:06
        Jokes笑話
        “最確切”的幸福觀感——我們的致富訂單
        懲罰
        趣味(語文)(2018年1期)2018-05-25 03:09:58
        基于自適應(yīng)遺傳算法的CSAMT一維反演
        一種基于遺傳算法的聚類分析方法在DNA序列比較中的應(yīng)用
        基于遺傳算法和LS-SVM的財(cái)務(wù)危機(jī)預(yù)測
        基于改進(jìn)的遺傳算法的模糊聚類算法
        国产91成人自拍视频| 亚洲综合成人婷婷五月网址| 97午夜理论片影院在线播放| 美女高潮无遮挡免费视频 | 久久久人妻精品一区bav| 精品国产三级a∨在线欧美| 夜夜高潮夜夜爽夜夜爱爱| 四虎影视久久久免费| 熟女不卡精品久久av| 免费毛儿一区二区十八岁| 天天鲁一鲁摸一摸爽一爽| 国产a级精精彩大片免费看| 丰满人妻一区二区三区52| 国产精品国产三级国产aⅴ下载| 亚洲精品字幕| 97在线视频免费| 日韩女优一区二区在线观看| 国产私人尤物无码不卡| 中文无码日韩欧| 香蕉视频一级| 日本一区二区精品色超碰| 久久久国产精品| 9lporm自拍视频区| 国产美女裸身网站免费观看视频| av免费在线播放观看| 国产精品爽爽久久久久久竹菊| 少妇高潮惨叫喷水在线观看| 国产三级国产精品三级在专区| 亚洲精品有码日本久久久| 国产午夜精品一区二区三区| 精品人妻中文av一区二区三区| 久久夜色精品国产三级| 中文字幕日韩精品有码视频| 国产人在线成免费视频| 四虎无码精品a∨在线观看| 亚洲国产中文字幕一区| 久久精品国产精品国产精品污| 国产艳妇av在线出轨| 在线观看一区二区蜜桃| 亚洲成av人影院| 久久精品国产亚洲AV高清特级|