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

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

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

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

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

問題3.試用你們在求解問題2中所使用的方法、算法或模型求解下表中20個任務的情況。任務1車間23459567891011121314151617181920867111615169163222651310111515179813568532印刷車間31056裝訂車間81296115232632261打包車間21553101151010問題4.對于問題3中的20個任務，請設(shè)計一個加工方案使得盡量多的任務在120天內(nèi)完成加工（每項任務均包括印刷、裝訂和打包）。

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

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

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

201*年7月19日

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

摘要

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

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

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

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

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

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

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

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

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

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

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

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

二、問題分析

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

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

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

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

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

三、模型假設(shè)

1、假設(shè)每一項任務依次經(jīng)過印刷車間、裝訂車間和打包車間順序進行；

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

3、假設(shè)對于一個任務不同車間之間可以間隔若干天開始，也可以連續(xù)依次進行；

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

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

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

四、符號說明

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

問題一：

5．1．1建模思路

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

5．1．2模型建立

步驟1：將3個車間系統(tǒng)地組成兩個工作階段：MA和MB，MA和MB對應任務時間：

tAti1ti2，tBti2ti3；

令

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

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

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

則csik可按如下公式計算：

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

Fmaxcsn3；

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

5．1．3模型求解

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

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

任務3時間開始時間1印刷車間1至5裝訂車間6至14打包車間15至19結(jié)束時間19問題二：

5．2．1建模思路

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

5．2．2模型建立

步驟1：將3個車間系統(tǒng)地組成兩個工作階段：MA和MB，MA和MB對應任務時間：

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任務具體的加工方案二步驟2：對U中的任務按tA非減順序排序得到U‘。步驟3：對V中的任務按tB非增順序排序V‘。

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

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

則csik可按如下公式計算：

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

Fmaxcsn3；

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

5．2．3模型求解

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

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

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

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

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

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

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

5．3．3模型求解

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

具體的加工方案：任務時間開始時間81123355161919至2426至3314213151010至印刷車間1至23至45至9186至12至21至裝訂車間3至51120252536465625至36至46至56至3545557036至49至61至71至486069打包車間結(jié)束時間任務時間開始時間印刷車間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至打包車間至至1141179496101109106111結(jié)束時間9496101106109111114117表六：加工天數(shù)小于120最多任務具體加工方案79至裝訂車間8493至99至105至98104107問題四：

5．4．1建模思路

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

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

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

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

5．5．1建模思路

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

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

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

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

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

6．1模型評價

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

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

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

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

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

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

參考文獻

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

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

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

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

附錄

問題一：

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);

運行結(jié)果：

optim_Fmax=57optim_seq=33552411466c=

51419141929243651274453335056445257

問題二：

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);

運行結(jié)果：

optim_Fmax=157optim_seq=8143519217151211161810147201*69c=

25114111692025182524334534466145597658749374901098510511895114126110119136118125143121133145127139148132145150137148152140150154151153155154156157

問題三：

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

第四問：

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)

運行結(jié)果：

Fmax=157ds=

2491824324253668293103118121127132137140151154

5112025333954678298113122127135141147150152154156

11162535455269841011171261341441461491511531551561

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

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

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

• 上一篇：201*年農(nóng)機購置補貼工作匯報
• 下一篇：印刷廠裝訂崗位職責