印刷廠任務(wù)的最優(yōu)調(diào)度問(wèn)題

印刷廠任務(wù)的最優(yōu)調(diào)度問(wèn)題

某印刷廠有6項(xiàng)加工任務(wù)，各項(xiàng)任務(wù)對(duì)印刷車(chē)間和裝訂車(chē)間所需時(shí)間（單位為：天）如下表所示：任務(wù)車(chē)間印刷車(chē)間裝訂車(chē)間138210123594665956112注：1.不同任務(wù)不能同時(shí)共享同一車(chē)間；2.一旦某項(xiàng)任務(wù)進(jìn)入某一車(chē)間，該任務(wù)就必須連續(xù)被執(zhí)行（不允許被其它任務(wù)打斷）；3.每一項(xiàng)任務(wù)必須先經(jīng)過(guò)印刷車(chē)間，等該項(xiàng)任務(wù)在印刷車(chē)間完成全部印刷之后才可以進(jìn)入裝訂車(chē)間（印刷和裝訂之間可以間隔若干天，也可以連續(xù)依次進(jìn)行）。

問(wèn)題1.試設(shè)計(jì)一個(gè)加工方案使得完成這6項(xiàng)任務(wù)總共需要的天數(shù)盡量少。

問(wèn)題2.現(xiàn)接到通知，除了印刷和裝訂之外，每一項(xiàng)加工任務(wù)均需要在裝訂車(chē)間完成該任務(wù)的全部裝訂之后進(jìn)入打包車(chē)間打包（裝訂和打包之間可以間隔若干天，也可以連續(xù)依次進(jìn)行）。已知這6項(xiàng)任務(wù)對(duì)打包車(chē)間所需時(shí)間依次為2天、15天、5天、3天、10天和1天。在考慮打包操作的情況下，試設(shè)計(jì)一個(gè)加工方案使得完成這6項(xiàng)任務(wù)總共需要的天數(shù)盡量少。

問(wèn)題3.試用你們?cè)谇蠼鈫?wèn)題2中所使用的方法、算法或模型求解下表中20個(gè)任務(wù)的情況。任務(wù)1車(chē)間23459567891011121314151617181920867111615169163222651310111515179813568532印刷車(chē)間31056裝訂車(chē)間81296115232632261打包車(chē)間21553101151010問(wèn)題4.對(duì)于問(wèn)題3中的20個(gè)任務(wù)，請(qǐng)?jiān)O(shè)計(jì)一個(gè)加工方案使得盡量多的任務(wù)在120天內(nèi)完成加工（每項(xiàng)任務(wù)均包括印刷、裝訂和打包）。

擴(kuò)展閱讀：印刷廠任務(wù)的最優(yōu)調(diào)度問(wèn)題論文

數(shù)模第四次培訓(xùn)論文

論文題目：印刷廠任務(wù)的最優(yōu)調(diào)度問(wèn)題

201*年7月19日

印刷廠任務(wù)的最優(yōu)調(diào)度問(wèn)題

摘要

本文主要研究印刷廠任務(wù)排序問(wèn)題，以按照實(shí)際條件合理調(diào)度為目標(biāo)，解決編制流水作業(yè)計(jì)劃。全文中主要采用CDS算法結(jié)合Johnson算法得到給定任務(wù)的最優(yōu)加工順序，從而用時(shí)間統(tǒng)計(jì)法得出最少的加工天數(shù)和具體的加工方案，整個(gè)過(guò)程用Matlab軟件編程實(shí)現(xiàn)，其中Johnson程序作為核心程序被多次調(diào)用。

對(duì)于問(wèn)題一：本題建立Conway模型，即n/m/A/B模型，據(jù)題意知n為6，m為3，A為F代表流水作業(yè)，B為Fmax。首先應(yīng)用CDS算法將三個(gè)車(chē)間系統(tǒng)地組成兩組，產(chǎn)生2個(gè)兩臺(tái)機(jī)器問(wèn)題的集合，然后利用Johnson的兩個(gè)車(chē)間算法得到2個(gè)加工順序，最后通過(guò)比較流程時(shí)間，選擇小值對(duì)應(yīng)加工順序作為最優(yōu)加工順序，從而采用時(shí)間統(tǒng)計(jì)法得到最少的加工天數(shù)和具體的加工方案。代入Matlab軟件編程得到所有結(jié)果：min(Fmin)=57,，最優(yōu)任務(wù)加工順序?yàn)?，5，2，4，1，6或3，5，2，1，4，6。

對(duì)于問(wèn)題二：采用與問(wèn)題一類似的Conway模型：20/3/F/Fmax模型。采用CDS算法結(jié)合Johnson算法得到最優(yōu)加工順序，從而應(yīng)用時(shí)間統(tǒng)計(jì)法得到最少的加工天數(shù)和具體的加工方案。應(yīng)用Matlab軟件編程得到結(jié)果：min(Fmin)=157，最優(yōu)任務(wù)加工順序?yàn)椋?，14，3，5，19，2，17，15，12，11，16，18，10，1，4，7，20，13，6，9。

對(duì)于問(wèn)題三：本題建立循環(huán)遍歷模型。采用循環(huán)法加隨機(jī)取矩陣法構(gòu)造任務(wù)序號(hào)和任務(wù)個(gè)數(shù)不一樣的任務(wù)矩陣，然后采用上述的CDS算法結(jié)合Johnson算法得到對(duì)應(yīng)不一樣的任務(wù)安排方案，從每次得到的排序方案中用時(shí)間統(tǒng)計(jì)法得到對(duì)應(yīng)的加工天數(shù)，將所得結(jié)果比較，取加工天數(shù)小于（或等于）120的天數(shù)對(duì)應(yīng)的最多任務(wù)的方案。應(yīng)用Matlab編程得到結(jié)果：min(Fmin)=117，最多任務(wù)個(gè)數(shù)為17，最優(yōu)任務(wù)加工順序?yàn)?，12，3，5，16，14，2，13，15，10，1，4，7，17，11，6，9。

對(duì)于問(wèn)題四：采用調(diào)試法解決從第50天到第60天這個(gè)長(zhǎng)度為11天的時(shí)間里每個(gè)車(chē)間放假2天，使得完成20項(xiàng)任務(wù)總共需要的天數(shù)盡量少并使對(duì)工程的影響盡量小的問(wèn)題。根據(jù)問(wèn)題二得到具體的加工方案，可知從第13號(hào)任務(wù)起出現(xiàn)在第50天到第60天，則建立循環(huán)調(diào)用第13號(hào)任務(wù)從頭開(kāi)始插入，依次循環(huán)，直至出現(xiàn)三個(gè)車(chē)間時(shí)間在第50天到第60天出現(xiàn)重疊的情況，放假期即為這些重疊天數(shù)，使總共需要的天數(shù)最少。應(yīng)用Matlab編程得到結(jié)果：調(diào)整后的任務(wù)加工順序?yàn)椋?，14，3，5，19，10，2，17，15，12，11，16，18，1，4，7，20，13，6，9。印刷車(chē)間放假時(shí)間為第54，55天，裝訂車(chē)間放假時(shí)間為第55，56天，打包車(chē)間放假時(shí)間為第53，54天，完成任務(wù)時(shí)間min(Fmin)=159。

對(duì)于問(wèn)題五：采用的方法與問(wèn)題四相同，結(jié)果為印刷車(chē)間放假時(shí)間為第54，55，56天，裝訂車(chē)間放假時(shí)間為第55，56，57天，打包車(chē)間放假時(shí)間為第53，54，55天，完成任務(wù)時(shí)間min(Fmin)=160。

關(guān)鍵詞：Conway模型；CDS算法；Johnson算法；時(shí)間統(tǒng)計(jì)法；Matlab軟件一、問(wèn)題重述

某印刷廠共有3個(gè)車(chē)間，分別為印刷車(chē)間、裝訂車(chē)間和打包車(chē)間。每一項(xiàng)任務(wù)必須依次經(jīng)過(guò)印刷車(chē)間、裝訂車(chē)間和打包車(chē)間。由于技術(shù)原因，每一項(xiàng)任務(wù)必須在印刷車(chē)間完成該任務(wù)的全部印刷之后才可以進(jìn)入裝訂車(chē)間（印刷和裝訂之間可以間隔若干天，也可以連續(xù)依次進(jìn)行）；每一項(xiàng)任務(wù)必須在裝訂車(chē)間完成該任務(wù)的全部裝訂之后才可以進(jìn)入打包車(chē)間（裝訂和打包之間可以間隔若干天，也可以連續(xù)依次進(jìn)行）；不同的任務(wù)不能同時(shí)共享同一車(chē)間；一旦某項(xiàng)任務(wù)進(jìn)入某一車(chē)間，該任務(wù)就必須連續(xù)被執(zhí)行，不允許被其它任務(wù)或事件打斷。

該印刷廠各車(chē)間目前均處于空閑狀態(tài)，沒(méi)有任務(wù)需要加工。印刷車(chē)間將來(lái)開(kāi)工的那天記為第1天。

問(wèn)題1.現(xiàn)接到6項(xiàng)加工任務(wù)，各項(xiàng)任務(wù)對(duì)各車(chē)間所需的時(shí)間（單位為：天）如表1所示。試設(shè)計(jì)一個(gè)加工方案（一個(gè)完整的加工方案應(yīng)該包括每一項(xiàng)任務(wù)在各個(gè)車(chē)間中的開(kāi)始加工時(shí)間和完成時(shí)間）使得完成這6項(xiàng)任務(wù)總共需要的天數(shù)盡量少。任務(wù)車(chē)間印刷車(chē)間裝訂車(chē)間打包車(chē)間13822101215359546635951061121表一第1至第6任務(wù)對(duì)應(yīng)車(chē)間時(shí)間問(wèn)題2.問(wèn)題1中的6項(xiàng)任務(wù)還沒(méi)有下達(dá)到車(chē)間，現(xiàn)又接到14項(xiàng)加工任務(wù)，各項(xiàng)任務(wù)對(duì)各車(chē)間所需的時(shí)間（單位為：天）如表2所示。試設(shè)計(jì)一個(gè)加工方案使得完成這20項(xiàng)任務(wù)總共需要的天數(shù)盡量少。任務(wù)車(chē)間印刷車(chē)間裝訂車(chē)間打包車(chē)間7562823693211011121314151617181920867111615169163222651310111561591358178151010532表二第7至第20任務(wù)對(duì)應(yīng)車(chē)間時(shí)間問(wèn)題3.對(duì)于問(wèn)題2中所考慮的20個(gè)任務(wù)，請(qǐng)?jiān)O(shè)計(jì)一個(gè)加工方案使得盡量多的任務(wù)在120天內(nèi)（含第120天）完成加工。

問(wèn)題4.為了工人的健康，印刷廠工會(huì)討論決定從第50天到第60天這個(gè)長(zhǎng)度為11天的時(shí)間里每個(gè)車(chē)間放假2天。為了盡量把放假對(duì)印刷廠的生產(chǎn)進(jìn)度造成的影響降到最低，工會(huì)決定把具體的放假時(shí)間交給印刷廠調(diào)度員來(lái)決定，并要求每個(gè)車(chē)間放假的這2天必須是連續(xù)的2天，每個(gè)車(chē)間的放假起止時(shí)間可以不一樣。請(qǐng)你們幫助印刷廠調(diào)度員來(lái)制定一個(gè)包含每個(gè)車(chē)間放假方案的任務(wù)加工方案使得完成問(wèn)題2中的這20項(xiàng)任務(wù)總共需要的天數(shù)盡量少。

問(wèn)題5.在問(wèn)題4中，如果每個(gè)車(chē)間的放假天數(shù)不是2天而是連續(xù)的3天，請(qǐng)?jiān)趩?wèn)題4中其余條件和要求不變的情況下重新制定一個(gè)包含每個(gè)車(chē)間放假方案的任務(wù)加工方案使得完成問(wèn)題2中的這20項(xiàng)任務(wù)總共需要的天數(shù)盡量少。

二、問(wèn)題分析

本題所涉及的為流水作業(yè)排序問(wèn)題，其基本特征是每個(gè)任務(wù)的加工路線為一致的，且不同的任務(wù)不能同時(shí)共享同一車(chē)間。加工路線一致，是指任務(wù)的車(chē)間流向一致；不能共享同一車(chē)間，即下一個(gè)任務(wù)在上一個(gè)任務(wù)完成該車(chē)間加工后方可進(jìn)入。

下面將結(jié)合問(wèn)題提及主要算法進(jìn)行分析。2．1Conway模型與編制流水作業(yè)計(jì)劃

Conway模型，即n/m/A/B模型貫穿于本文，目標(biāo)函數(shù)是使加工周期時(shí)間最短：從第一個(gè)工件在第一個(gè)車(chē)間開(kāi)始加工時(shí)算起，到最后一個(gè)任務(wù)在最后一個(gè)車(chē)間上完成加工時(shí)為止所經(jīng)過(guò)的時(shí)間。編制流水作業(yè)計(jì)劃：包括確定工件的加工順序，而且還包括確定機(jī)器加工每個(gè)工件的開(kāi)始時(shí)間和完成時(shí)間。在問(wèn)題一與問(wèn)題二中，本文可采用CDS算法結(jié)合Johnson算法、時(shí)間統(tǒng)計(jì)法求解，用Matlab軟件編程得出近似解。其中編寫(xiě)的Johnson程序?yàn)楹诵某绦颍�在�?wèn)題三、四、五中需調(diào)用此程序。

2．2循環(huán)遍歷模型

在問(wèn)題三、問(wèn)題四與問(wèn)題五中，首先將20個(gè)任務(wù)對(duì)應(yīng)3個(gè)車(chē)間的時(shí)間模擬成3行20列的矩陣，建立的循環(huán)遍歷模型主要思想為：采用循環(huán)法加隨機(jī)取矩陣法構(gòu)造任務(wù)序號(hào)和任務(wù)個(gè)數(shù)不一樣的任務(wù)矩陣。然后調(diào)用上述Johnson程序，代入新的任務(wù)矩陣，得出所有新的排序方案，再?gòu)闹腥〕龇�合題目的結(jié)果。

三、模型假設(shè)

1、假設(shè)每一項(xiàng)任務(wù)依次經(jīng)過(guò)印刷車(chē)間、裝訂車(chē)間和打包車(chē)間順序進(jìn)行；

2、假設(shè)不同的任務(wù)不能同時(shí)共享同一車(chē)間；

3、假設(shè)對(duì)于一個(gè)任務(wù)不同車(chē)間之間可以間隔若干天開(kāi)始，也可以連續(xù)依次進(jìn)行；

4、假設(shè)每個(gè)車(chē)間任務(wù)一旦開(kāi)始就必須連續(xù)被執(zhí)行，不允許被其它任務(wù)或事件打斷；

5、假設(shè)每個(gè)人任務(wù)在規(guī)定的時(shí)間均能按時(shí)完成；6、車(chē)間生產(chǎn)時(shí)間與任務(wù)排序無(wú)關(guān)；

6、假設(shè)每個(gè)任務(wù)從第i天早上開(kāi)始第j天晚上結(jié)束。

四、符號(hào)說(shuō)明

符號(hào)tij含義說(shuō)明第i任務(wù)對(duì)應(yīng)第j車(chē)間所需時(shí)間j1,2,3分組后得到的新集合k1,2MkFmax每種順序下最大流程時(shí)間最優(yōu)加工順序后排在第i位的加工任務(wù)任務(wù)si在車(chē)間Mk里的完工時(shí)間任務(wù)si在Mk里的加工時(shí)間sicsiktsik五、模型的建立與求解

問(wèn)題一：

5．1．1建模思路

為使完成6項(xiàng)任務(wù)總共需要的天數(shù)盡量少，首先需找到使得總加工天數(shù)最少的最優(yōu)加工順序，然后按照最佳加工順序求解最少的加工天數(shù)和具體的加工方案。本文將采用CDS算法結(jié)合Johnson算法、時(shí)間統(tǒng)計(jì)法以最少總時(shí)間為目標(biāo)求解，首先應(yīng)用CDS算法將三個(gè)車(chē)間系統(tǒng)地組成兩組，產(chǎn)生2個(gè)兩臺(tái)機(jī)器問(wèn)題的集合，然后利用Johnson的兩個(gè)車(chē)間算法得到2個(gè)加工順序，最后通過(guò)比較流程時(shí)間，選擇小值對(duì)應(yīng)加工順序作為最優(yōu)加工順序，從而得到最少的加工天數(shù)和具體的加工方案。應(yīng)用Matlab軟件編程得到所有結(jié)果。

5．1．2模型建立

步驟1：將3個(gè)車(chē)間系統(tǒng)地組成兩個(gè)工作階段：MA和MB，MA和MB對(duì)應(yīng)任務(wù)時(shí)間：

tAti1ti2，tBti2ti3；

令

U{itAtB}，V{itAtB}(i1,..,6)。步驟2：對(duì)U中的任務(wù)按tA非減順序排序得到U‘。步驟3：對(duì)V中的任務(wù)按tB非增順序排序V‘。

步驟4：將有序集U‘放到V‘之前構(gòu)成工件的最優(yōu)加工順序S。步驟5：根據(jù)最優(yōu)加工順序計(jì)算最長(zhǎng)流程時(shí)間。設(shè)6個(gè)任務(wù)的加工順序?yàn)?

S{s1,s2,...,s6}；

則csik可按如下公式計(jì)算：

cs11ts11cs1kcs1,k1ts1k,k2,...,3...........................................(1)csi1csi11tsi1,i2,...,6...............................................(2)csikmax{csi1k,csi,k1}tsik,i2,...,6;k2,...,3.........(3)由（3）式得最大流程時(shí)間為：

Fmaxcsn3；

i而且可以求得個(gè)任務(wù)在各個(gè)車(chē)間的完工時(shí)間csk,i1,2,...,6;k1,2,...,3。步驟6：代入思想應(yīng)用Matlab軟件編程，輸出最優(yōu)任務(wù)加工順序、最少的加工天數(shù)和每個(gè)任務(wù)具體工作時(shí)間安排。

5．1．3模型求解

通過(guò)Matlab編程(見(jiàn)附錄),運(yùn)行得到結(jié)果：min(Fmin)=57，最優(yōu)任務(wù)加工順序?yàn)椋?，5，2，4，1，6或3，5，2，1，4，6。

具體的加工方案：任務(wù)3時(shí)間開(kāi)始時(shí)間1印刷車(chē)間1至5裝訂車(chē)間6至14打包車(chē)間15至19結(jié)束時(shí)間19524163434至4450至5157576156至1415至2415至1925至3620至2937至512951252125至3031至3337至4242至4952至5455至565356表三：第1至第6任務(wù)具體的加工方案一

任務(wù)3時(shí)間開(kāi)始時(shí)間1印刷車(chē)間1至5裝訂車(chē)間6至14打包車(chē)間15至19結(jié)束時(shí)間19問(wèn)題二：

5．2．1建模思路

問(wèn)題二在問(wèn)題一的基礎(chǔ)上添加了任務(wù)個(gè)數(shù)，故求解方法類似于問(wèn)題一，首先采用CDS算法結(jié)合Johnson算法找到使得總加工天數(shù)最少的最優(yōu)加工順序，然后應(yīng)用時(shí)間統(tǒng)計(jì)法遞推法，按照最佳加工順序求解最少的加工天數(shù)，得到具體的加工方案。應(yīng)用Matlab軟件編程得到所有結(jié)果。

5．2．2模型建立

步驟1：將3個(gè)車(chē)間系統(tǒng)地組成兩個(gè)工作階段：MA和MB，MA和MB對(duì)應(yīng)任務(wù)時(shí)間：

tAti1ti2，tBti2ti3；

令

U{itAtB}，V{itAtB}(i1,..,6)。

521466156至1415至2415至1925至3620至2937至51295125283425至2728至3334至4437至4445至5051至5252至5354至5657535657表四：第1至第6任務(wù)具體的加工方案二步驟2：對(duì)U中的任務(wù)按tA非減順序排序得到U‘。步驟3：對(duì)V中的任務(wù)按tB非增順序排序V‘。

步驟4：將有序集U‘放到V‘之前構(gòu)成工件的最優(yōu)加工順序S。步驟5：根據(jù)最優(yōu)加工順序計(jì)算最長(zhǎng)流程時(shí)間。設(shè)6個(gè)任務(wù)的加工順序?yàn)?

S{s1,s2,...,s20}；

則csik可按如下公式計(jì)算：

cs11ts11cs1kcs1,k1ts1k,k2,...,3...........................................(1)csi1csi11tsi1,i2,...,6...............................................(2)csikmax{csi1k,csi,k1}tsik,i2,...,6;k2,...,3.........(3)由（3）式得最大流程時(shí)間為：

Fmaxcsn3；

而且可以求得個(gè)任務(wù)在各個(gè)車(chē)間的完工時(shí)間csik(i1,...,20，k1,2,3)。步驟6：代入思想應(yīng)用Matlab軟件編程，輸出最優(yōu)任務(wù)加工順序、最少的加工天數(shù)和每個(gè)任務(wù)具體工作時(shí)間安排。

5．2．3模型求解

通過(guò)Matlab編程(見(jiàn)附錄),運(yùn)行得到結(jié)果：min(Fmin)=157，最優(yōu)任務(wù)加工順序?yàn)椋?，14，3，5，19，2，17，15，12，11，16，18，10，1，4，7，20，13，6，9。

具體的加工方案：任務(wù)時(shí)間開(kāi)始時(shí)間81433至46至1112至1616189696至355至912至2021至252510111111至51921715121111至印刷車(chē)間23至裝訂車(chē)間5打包車(chē)間6至11101910至19至182421至26至253326至36至3545351119119至454122122至253525至35至344535至47至465946至62至6176617128128至76201*3133至結(jié)束時(shí)間11任務(wù)16時(shí)間開(kāi)始時(shí)間8686至印刷車(chē)間9546597546至59至75至58748560至75至91至749010511077至94至至931091189310911813138138至6141141至9152152至1101181211271321371401061151201*6134140146149裝訂車(chē)間至至至至至至至至114119125133139145148150119127137144146149151153打包車(chē)間至至至至至至至至126136143145148150152154結(jié)束時(shí)間126136143145148150152154表五：第1至第20任務(wù)具體的加工方案安排問(wèn)題三：

151152至153155155154155至1561571575．3．1建模思路

若得到任務(wù)的加工順序，則可求得對(duì)應(yīng)的加工天數(shù)。本文采用循環(huán)法加隨機(jī)取矩陣法構(gòu)造任務(wù)序號(hào)和任務(wù)個(gè)數(shù)不一樣的任務(wù)矩陣，然后采用上述的CDS算法結(jié)合Johnson算法得到對(duì)應(yīng)不一樣的任務(wù)安排方案，從每次得到的排序方案中求解得到對(duì)應(yīng)的加工天數(shù)，將所得結(jié)果比較，取加工天數(shù)小于（或等于）120的天數(shù)對(duì)應(yīng)的最多任務(wù)的方案。

在構(gòu)造新矩陣時(shí)，為方便使用隨機(jī)函數(shù)組合新矩陣，將20個(gè)任務(wù)3個(gè)車(chē)間對(duì)應(yīng)的3行20列矩陣簡(jiǎn)化為20列的行矩陣；根據(jù)問(wèn)題二中的加工方案安排可知在120天內(nèi)的盡量多的任務(wù)數(shù)大于10，所以在采用循環(huán)時(shí)取任務(wù)個(gè)數(shù)為10至19。對(duì)于10至19每個(gè)任務(wù)數(shù)，用隨機(jī)矩陣從20列中取出對(duì)應(yīng)的任務(wù)數(shù)，代入CDS算法得到對(duì)應(yīng)的加工天數(shù)與最優(yōu)加工順序，依次循環(huán)，取出加工天數(shù)小于（或等于）120的天數(shù)對(duì)應(yīng)的最多任務(wù)的方案。5．3．2模型建立

設(shè)立循環(huán)計(jì)數(shù)：k2,...,11；

用隨機(jī)矩陣從20列中取出對(duì)應(yīng)的任務(wù)數(shù)：brandperm(20)；調(diào)用CDS算法結(jié)合Johnson算法，按照上述問(wèn)題二中方法進(jìn)行。

5．3．3模型求解

通過(guò)Matlab編程(見(jiàn)附錄),運(yùn)行得到結(jié)果：min(Fmin)=117，最多任務(wù)個(gè)數(shù)為17，最優(yōu)任務(wù)加工順序?yàn)椋?，12，3，5，16，14，2，13，15，10，1，4，7，17，11，6，9。

具體的加工方案：任務(wù)時(shí)間開(kāi)始時(shí)間81123355161919至2426至3314213151010至印刷車(chē)間1至23至45至9186至12至21至裝訂車(chē)間3至51120252536465625至36至46至56至3545557036至49至61至71至486069打包車(chē)間結(jié)束時(shí)間任務(wù)時(shí)間開(kāi)始時(shí)間印刷車(chē)間6至1111107171至7812至161617979至8185至9221至26至2535253548278836至4545179393至9749至64至70至78至6368778763687787119898至1006101101至111112至1139112112至114115至11682至88至8792108至10910511088至95至99至108至打包車(chē)間至至1141179496101109106111結(jié)束時(shí)間9496101106109111114117表六：加工天數(shù)小于120最多任務(wù)具體加工方案79至裝訂車(chē)間8493至99至105至98104107問(wèn)題四：

5．4．1建模思路

本文采用調(diào)試法解決從第50天到第60天這個(gè)長(zhǎng)度為11天的時(shí)間里每個(gè)車(chē)間放假2天，使得完成20項(xiàng)任務(wù)總共需要的天數(shù)盡量少問(wèn)題。根據(jù)問(wèn)題二得到的第1至第20任務(wù)具體的加工方案，可知從第13號(hào)任務(wù)起出現(xiàn)在第50天到第60天，則建立循環(huán)調(diào)用第13號(hào)任務(wù)從頭開(kāi)始插入，依次循環(huán)，直至出現(xiàn)三個(gè)車(chē)間時(shí)間在第50天到第60天出現(xiàn)重疊的情況，放假期即為這些重疊天數(shù)，使得總共需要的天數(shù)最少。5．4．2模型建立

問(wèn)題四要求的是制定一個(gè)包含每個(gè)車(chē)間放假方案的任務(wù)加工方案，使得完成問(wèn)題2中的這20項(xiàng)任務(wù)總共需要的天數(shù)盡量少，考慮到每個(gè)車(chē)間在50到60天這個(gè)時(shí)間段連續(xù)放兩天假，而各個(gè)車(chē)間的任務(wù)一旦執(zhí)行就不能中斷，因此，我們需要在模型一的基礎(chǔ)上優(yōu)化求解。

由表5，可以得出每個(gè)任務(wù)在各車(chē)間的結(jié)束時(shí)間，為滿足放假時(shí)間段的限制，找到在49至58天完工的對(duì)應(yīng)任務(wù)項(xiàng)。據(jù)表可知，排名在第五項(xiàng)任務(wù)前的各任務(wù)對(duì)應(yīng)完工時(shí)間都小于49，為了盡量把放假對(duì)印刷廠的生產(chǎn)進(jìn)度造成的影響降到最低，隨機(jī)取出后15項(xiàng)任務(wù)中的一項(xiàng)排在第六名，而原方案中第五項(xiàng)任務(wù)之后的各項(xiàng)依次向后排一位。因此，得出新方案中排在第六的任務(wù)對(duì)應(yīng)完成時(shí)間和新的排序方案，依次類推，得到新排名七至二十任務(wù)的對(duì)應(yīng)完成時(shí)間及方案。從中篩選出在49至58天完工的對(duì)應(yīng)任務(wù)項(xiàng)的完成時(shí)間，最后取使完成所有任務(wù)總共需要的天最少的方案即為所求。根據(jù)得到的最少天數(shù)方案將對(duì)應(yīng)任務(wù)項(xiàng)所需時(shí)間加兩天代入原方案求解（相應(yīng)語(yǔ)句在程序中實(shí)現(xiàn)），得出相應(yīng)各項(xiàng)任務(wù)的結(jié)束時(shí)間即得到所求方案。5．4．3模型求解

應(yīng)用Matlab編程得到結(jié)果：調(diào)整后的任務(wù)加工順序?yàn)椋?，14，3，5，19，10，2，17，15，12，11，16，18，1，4，7，20，13，6，9。印刷車(chē)間放假時(shí)間為第54，55天，裝訂車(chē)間放假時(shí)間為第55，56天，打包車(chē)間放假時(shí)間為第53，54天，完成任務(wù)時(shí)間min(Fmin)=159。問(wèn)題五：

5．5．1建模思路

問(wèn)題五與問(wèn)題四的思想一致，只是在其基礎(chǔ)上將連續(xù)放假兩天改為三天，其余條件和要求不變，制定一個(gè)包含每個(gè)車(chē)間放假方案的任務(wù)加工方案使得完成問(wèn)題2中的所有任務(wù)總共需要的天數(shù)最少，根據(jù)得到的最少天數(shù)方案將對(duì)應(yīng)任務(wù)項(xiàng)所需時(shí)間加三天代入原方案求解即可。5．5．2模型建立

問(wèn)題五要求的是制定一個(gè)包含每個(gè)車(chē)間放假方案的任務(wù)加工方案，使得完成問(wèn)題2中的這20項(xiàng)任務(wù)總共需要的天數(shù)盡量少，考慮到每個(gè)車(chē)間在50到60天這個(gè)時(shí)間段連續(xù)放兩天假，而各個(gè)車(chē)間的任務(wù)一旦執(zhí)行就不能中斷，因此，我們需要在模型一的基礎(chǔ)上優(yōu)化求解。

由表5，可以得出每個(gè)任務(wù)在各車(chē)間的結(jié)束時(shí)間，為滿足放假時(shí)間段的限制，找到在49至58天完工的對(duì)應(yīng)任務(wù)項(xiàng)。據(jù)表可知，排名在第五項(xiàng)任務(wù)前的各任務(wù)對(duì)應(yīng)完工時(shí)間都小于49，為了盡量把放假對(duì)印刷廠的生產(chǎn)進(jìn)度造成的影響降到最低，隨機(jī)取出后15項(xiàng)任務(wù)中的一項(xiàng)排在第六名，而原方案中第五項(xiàng)任務(wù)之后的各項(xiàng)依次向后排一位。因此，得出新方案中排在第六的任務(wù)對(duì)應(yīng)完成時(shí)間和新的排序方案，依次類推，得到新排名七至二十任務(wù)的對(duì)應(yīng)完成時(shí)間及方案。從中篩選出在49至58天完工的對(duì)應(yīng)任務(wù)項(xiàng)的完成時(shí)間，最后取使完成所有任務(wù)總共需要的天最少的方案即為所求。根據(jù)得到的最少天數(shù)方案將對(duì)應(yīng)任務(wù)項(xiàng)所需時(shí)間加兩天代入原方案求解（相應(yīng)語(yǔ)句在程序中實(shí)現(xiàn)），得出相應(yīng)各項(xiàng)任務(wù)的結(jié)束時(shí)間即得到所求方案。5．5．3模型求解

應(yīng)用Matlab編程得到結(jié)果：調(diào)整后的任務(wù)加工順序?yàn)椋?，14，3，5，19，10，2，17，15，12，11，16，18，1，4，7，20，13，6，9。印刷車(chē)間放假時(shí)間為第54，55，56天，裝訂車(chē)間放假時(shí)間為第55，56,57天，打包車(chē)間放假時(shí)間為第53，54,55天，完成任務(wù)時(shí)間min(Fmin)=160。

六、模型的優(yōu)化與推廣

6．1模型評(píng)價(jià)

（1）所采用的CDS算法結(jié)合Johnson算法有效地解決了多個(gè)任務(wù)對(duì)應(yīng)多個(gè)車(chē)間最優(yōu)加工方案。

（2）軟件編程中使用循環(huán)語(yǔ)句遍歷所有情況，所得結(jié)果真實(shí)性較高。（3）CDS算法具有自組織、自適應(yīng)、自學(xué)習(xí)性與并行性而不需要求導(dǎo)或其他輔助知識(shí)，使問(wèn)題易于處理。6．2模型改進(jìn)

（1）Johnson法則只是一個(gè)充分條件，不是必要條件。不符合這個(gè)法則的加工順序，也可能是最優(yōu)順序。

（2）本模型中使用了大量的循環(huán)語(yǔ)句，導(dǎo)致軟件運(yùn)算量極大，故編程語(yǔ)句欠妥，需要進(jìn)一步討論改進(jìn)。6．3模型推廣

（1）本模型準(zhǔn)確性較高，可以推廣到其它流水線工作問(wèn)題上。

（2）根據(jù)實(shí)際情況，進(jìn)一步加強(qiáng)約束條件的嚴(yán)謹(jǐn)性，使得模型更加緊密，結(jié)果會(huì)得到進(jìn)一步優(yōu)化。

參考文獻(xiàn)

[1]陳桂明，戚紅雨，潘偉編著，Matlab數(shù)理統(tǒng)計(jì)（6.X），北京：科學(xué)出版社，201*。

[2]姜啟源，謝金星著，數(shù)學(xué)建模案例選集，北京：高等教育出版社，201*。[3]王沫然，MATLAB5.X與科學(xué)計(jì)算，北京：清華大學(xué)出版社，201*。

[4]李濤，賀勇軍，劉志儉等編著，Matlab工具箱應(yīng)用指南應(yīng)用數(shù)學(xué)篇，北京：電子工業(yè)出版社，201*。

[5]王振龍主編，時(shí)間序列分析，北京：中國(guó)統(tǒng)計(jì)出版社，201*。

附錄

問(wèn)題一：

functionexampleclc

T=[31056911812965221553101]";[n,m]=size(T);txm=[];Fmax=[];TUV=[];fork=1:m-1fori=1:n

tx(i,1)=sum(T(i,1:k));tx(i,2)=sum(T(i,m+1-k:m));end

[c,fmax,uv]=myjohnson(tx,T,n,m);Fmax=[Fmax,fmax];txm=[txm,tx];TUV=[TUV,uv];end

txm,Fmax,TUV

optim_Fmax=min(Fmax)ind=find(Fmax==optim_Fmax);optim_seq=TUV(:,ind)c

%*********************************************************function[c,f,UV]=myjohnson(tx,T,n,m);U=find(tx(:,1)tx(:,2));tU=tx(U,1);tV=tx(V,2);[stU,ind1]=sort(tU);

[stV,ind2]=sort(tV,"descend");UV=[U(ind1);V(ind2)];st=T(UV,:);

c(1,:)=cumsum(st(1,:));

c(2:n,1)=c(1,1)+cumsum(st(2:n,1));fori=2:nfork=2:m

c(i,k)=max(c(i-1,k),c(i,k-1))+st(i,k);endendf=c(end);

運(yùn)行結(jié)果：

optim_Fmax=57optim_seq=33552411466c=

51419141929243651274453335056445257

問(wèn)題二：

functionexampleclc

T=[31056911523811163213105

812965263261516263

21553101261791625102]";

[n,m]=size(T);txm=[];Fmax=[];TUV=[];fork=1:m-1fori=1:n

tx(i,1)=sum(T(i,1:k));tx(i,2)=sum(T(i,m+1-k:m));end

[c,fmax,uv]=myjohnson(tx,T,n,m);Fmax=[Fmax,fmax];txm=[txm,tx];TUV=[TUV,uv];end

txm,Fmax,TUV

optim_Fmax=min(Fmax)ind=find(Fmax==optim_Fmax);optim_seq=TUV(:,ind)c

%*********************************************************function[c,f,UV]=myjohnson(tx,T,n,m);U=find(tx(:,1)V=find(tx(:,1)>tx(:,2));tU=tx(U,1);tV=tx(V,2);[stU,ind1]=sort(tU);

[stV,ind2]=sort(tV,"descend");UV=[U(ind1);V(ind2)];st=T(UV,:);

c(1,:)=cumsum(st(1,:));

c(2:n,1)=c(1,1)+cumsum(st(2:n,1));fori=2:nfork=2:m

c(i,k)=max(c(i-1,k),c(i,k-1))+st(i,k);endendf=c(end);

運(yùn)行結(jié)果：

optim_Fmax=157optim_seq=8143519217151211161810147201*69c=

25114111692025182524334534466145597658749374901098510511895114126110119136118125143121133145127139148132145150137148152140150154151153155154156157

問(wèn)題三：

functionexample[Fmax,optim_seq,T]clcT=T";

[n,m]=size(T);txm=[];Fmax=[];TUV=[];fork=1:m-1fori=1:n

tx(i,1)=sum(T(i,1:k));

tx(i,2)=sum(T(i,m+1-k:m));end

[c,fmax,uv]=myjohnson(tx,T,n,m);Fmax=[Fmax,fmax];txm=[txm,tx];TUV=[TUV,uv];end

txm,Fmax,TUV

optim_Fmax=min(Fmax)ind=find(Fmax==optim_Fmax);optim_seq=TUV(:,ind)C

%*********************************************************

function[c,f,UV]=myjohnson(tx,T,n,m);U=find(tx(:,1)tx(:,2));tU=tx(U,1);tV=tx(V,2);[stU,ind1]=sort(tU);

[stV,ind2]=sort(tV,"descend");UV=[U(ind1);V(ind2)];st=T(UV,:);

c(1,:)=cumsum(st(1,:));

c(2:n,1)=c(1,1)+cumsum(st(2:n,1));fori=2:n

fork=2:m

c(i,k)=max(c(i-1,k),c(i,k-1))+st(i,k);endendf=c(end);

%*********************************************************

clear;clc

a=[31056911523811163213101110111565

81296526326151626159135813583

2155310126179162517815101510102]fori=1:500m=0;c=0;mmax=[];cmax=[];

b=randperm(20);c=a(:,b);

fork=2:11t=c(:,k:20);

[d,f,g]=example(Fmax,optim_seq,T);if(doptim_Fmax=117

optim_seq=8123516142131510147171169c=

2511411169202518253524334535486345606855697770758778849481929687981019210410697107109100109111111113114114116117

第四問(wèn)：

clc,clear

t=[31056911523811163213101115658129652632615162615913583215531012617916251781510102]"s=[8143519102171512111618147201*69]";

st=t(s,:);

[n,m]=size(st);

c(1,:)=cumsum(st(1,:));

c(2:n,1)=c(1,1)+cumsum(st(2:n,1));fori=2:n

fork=2:m

c(i,k)=max(c(i-1,k),c(i,k-1))+st(i,k);endend

ds=c"

Fmax=ds(end)

運(yùn)行結(jié)果：

Fmax=157ds=

2491824324253668293103118121127132137140151154

5112025333954678298113122127135141147150152154156

11162535455269841011171261341441461491511531551561

友情提示：本文中關(guān)于《印刷廠任務(wù)的最優(yōu)調(diào)度問(wèn)題》給出的范例僅供您參考拓展思維使用，印刷廠任務(wù)的最優(yōu)調(diào)度問(wèn)題：該篇文章建議您自主創(chuàng)作。

來(lái)源：網(wǎng)絡(luò)整理 免責(zé)聲明：本文僅限學(xué)習(xí)分享，如產(chǎn)生版權(quán)問(wèn)題，請(qǐng)聯(lián)系我們及時(shí)刪除。

《印刷廠任務(wù)的最優(yōu)調(diào)度問(wèn)題》由互聯(lián)網(wǎng)用戶整理提供,轉(zhuǎn)載分享請(qǐng)保留原作者信息,謝謝!
鏈接地址：http://www.weilaioem.com/gongwen/560058.html

• 上一篇：201*年農(nóng)機(jī)購(gòu)置補(bǔ)貼工作匯報(bào)
• 下一篇：印刷廠裝訂崗位職責(zé)