印刷厂任务的最优调度问题

某印刷厂有6项加工任务，各项任务对印刷车间和装订车间所需时间（单位为：天）如下表所示：任务车间印刷车间装订车间138210123594665956112注：

1.不同任务不能同时共享同一车间；

2.一旦某项任务进入某一车间，该任务就必须连续被执行（不允许被其它任务打断）；

3.每一项任务必须先经过印刷车间，等该项任务在印刷车间完成全部印刷之后才可以进入装订车间（印刷和装订之间可以间隔若干天，也可以连续依次进行）。

问题1.试设计一个加工方案使得完成这6项任务总共需要的天数尽量少。

问题2.现接到通知，除了印刷和装订之外，每一项加工任务均需要在装订车间完成该任务的全部装订之后进入打包车间打包（装订和打包之间可以间隔若干天，也可以连续依次进行）。已知这6项任务对打包车间所需时间依次为2天、15天、5天、3天、10天和1天。在考虑打包操作的情况下，试设计一个加工方案使得完成这6项任务总共需要的天数尽量少。

问题3.试用你们在求解问题2中所使用的方法、算法或模型求解下表中20个任务的情况。任务1车间23459567891011121314151617181920867111615169163222651310111515179813568532印刷车间31056装订车间81296115232632261打包车间21553101151010问题4.对于问题3中的20个任务，请设计一个加工方案使得尽量多的任务在120天内完成加工（每项任务均包括印刷、装订和打包）。

扩展阅读：论文

数模第四次培训论文

论文题目：

201*年7月19日

摘要

本文主要研究印刷厂任务排序问题，以按照实际条件合理调度为目标，解决编制流水作业计划。全文中主要采用cds算法结合johnson算法得到给定任务的最优加工顺序，从而用时间统计法得出最少的加工天数和具体的加工方案，整个过程用matlab软件编程实现，其中johnson程序作为核心程序被多次调用。

对于问题一：本题建立conway模型，即n/m/a/b模型，据题意知n为6，m为3，a为f代表流水作业，b为fmax。首先应用cds算法将三个车间系统地组成两组，产生2个两台机器问题的集合，然后利用johnson的两个车间算法得到2个加工顺序，最后通过比较流程时间，选择小值对应加工顺序作为最优加工顺序，从而采用时间统计法得到最少的加工天数和具体的加工方案。代入matlab软件编程得到所有结果：min（fmin）=57，，最优任务加工顺序为3，5，2，4，1，6或3，5，2，1，4，6。

对于问题二：采用与问题一类似的conway模型：20/3/f/fmax模型。采用cds算法结合johnson算法得到最优加工顺序，从而应用时间统计法得到最少的加工天数和具体的加工方案。应用matlab软件编程得到结果：min（fmin）=157，最优任务加工顺序为：8，14，3，5，19，2，17，15，12，11，16，18，10，1，4，7，20，13，6，9。

对于问题三：本题建立循环遍历模型。采用循环法加随机取矩阵法构造任务序号和任务个数不一样的任务矩阵，然后采用上述的cds算法结合johnson算法得到对应不一样的任务安排方案，从每次得到的排序方案中用时间统计法得到对应的加工天数，将所得结果比较，取加工天数小于（或等于）120的天数对应的最多任务的方案。应用matlab编程得到结果：min（fmin）=117，最多任务个数为17，最优任务加工顺序为8，12，3，5，16，14，2，13，15，10，1，4，7，17，11，6，9。