2016年武汉大学全国数模选拔.docx

PAGE PAGE 6 数学建模论文 题 目 任务车间调度问题 姓 名 张明一 　　　　 学 院 电气工程学院 　　　 专 业 电气工程及其自动化 学 号 2014302540027 　　 电 　　　 邮 箱 674611507@　 得 分 　　　　　　　　　 任务车间调度的最优模型 摘要： 根据问题“试制定墙纸在机器之间的印刷计划，以使订单尽快完成”可知，本题为建立最优化模型，求出墙纸加工时间最短的加工方案。 本题根据已知数据，结合问题中的具体要求，我根据题目要求最短时间为目标，用数学语言描述出墙纸加工顺序，加工时间，机器每次执行一个任务等的约束条件，建立墙纸加工方案的数学规划模型。借助lingo软件进行求解运算，得到其中的最优排序方案，使得这些墙纸加工任务所需要的总时间最短。 最后，根据建立的模型求解得三种墙纸在三台机器上所需要的最短总加工时间为97分钟，总加工时间最短的加工方案见文中的甘特图。 【关键词】任务车间调度　非线性规划模型　甘特图　LINGO  1 问题重述： 某墙纸生产厂接到三种类型墙纸的订单，第一种墙纸在蓝色背景上有黄色图案，第二种墙纸在绿色背景上有蓝色和黄色图案，第三种墙纸在黄色背景上有蓝色和绿色图案。在生产时，每种墙纸都是一个连续的纸卷，且将要通过三台机器，每台机器向墙纸上印刷不同的颜色。墙纸通过机器的顺序取决于墙纸的设计，对于第一种墙纸，先印刷蓝色背景，再印刷黄色图案；对于第二种墙纸，首先印刷绿色背景，然后先印刷蓝色图案，再印刷黄色图案；对于第三种墙纸，首先印刷黄色背景，然后先印刷蓝色图案，再印刷绿色图案。每一个工序的处理时间取决于需要向墙纸上印刷的对象。各种墙纸每种颜色的印刷时间如下表所示。每种颜色印刷需时（单位：分钟） 机器颜色墙纸1 墙纸2 墙纸3 1 绿色 - 10 17 2 蓝色 45 20 12 3 黄色 10 34 28 若每台机器同时只能处理一种墙纸，一种墙纸不能同时由多台机器进行处理，试制定墙纸在机器之间的印刷计划，以使订单尽快完成。 2 条件假设： （1）每个机器在同一时刻最多只能加工一个墙纸； （2）每个墙纸同一时刻最多只能被一台机器加工； （3）墙纸的加工过程需符合预先给定的工艺路线要求，同一个墙纸的不同工序不能同时加工； （4）工序一旦开始加工不能中断，直至加工完成； （5）各个墙纸之间相互独立，不存在顺序约束，相互之间没有优先级差别； （6）在零时刻，所有机器的初始状态均为空闲可用； （7）在零时刻，所有墙纸都到达系统可以加工； （8）墙纸的一道工序被加工完后即转移到下一道工序所需要的机器，之间的转移时间忽略不计。 （9）墙纸1没有绿色这道工艺，可以设定为印刷时间为0，不影响求解结果。 3 符号说明： 表示第i种墙纸开始被机器j处理的时刻 表示第i种墙纸被机器j处理结束的时刻 　表示第i种墙纸被机器j处理所需要的时间 T　　表示任务完成的总时间 4 问题分析： 此问题属于规划问题，目的是给出使加工时间最短的墙纸加工方案。 已知每种墙纸在各个加工工序所需要的时间，并且规定每台机器每次只能处理一个墙纸，每种墙纸按照给定处理步骤即：第一种墙纸，先印刷蓝色背景，再印刷黄色图案；第二种墙纸，首先印刷绿色背景，然后先印刷蓝色图案，再印刷黄色图案；第三种墙纸，首先印刷黄色背景，然后先印刷蓝色图案，再印刷绿色图案的方式进行，要求出加工所有墙纸所用的最短时间。要让总的加工时间最短，每种机器工作时间是连续的，即中途不允许在有生产任务有做相应任务的机器空闲时，机器不加工。总的时间就三种墙纸均被加工完成的时间。?通过分析知道此问题是一个规划问题。根据题目要求忽略次要影响因素，将主要因素翻译成数学语言，利用已有的数学知识，建立相应的模型。忽略了机器加工的准备时间以及机器可能出现故障等突发条件，以各种墙纸按自己的加工顺序及机器每次只能处理一个墙纸为主要约束条件，建立使得加工总用时最少的规划模型。 5 模型建立： 此问题是根据每种墙纸固有的加工顺序，通过合理的分配机器，选择出用时最少的方案。为了方便模型的建立及求解，我以每种墙纸各一个，机器有三个开始讨论。 要求得时间最少的加工方案的问题，转化为寻求哪个墙纸最后被加工，这个墙纸的被机器结束加工F时刻即为每个方案最终时间，所以目标函数转化为： Min T 任务完成的总时间为： T=Max{} i=1 2 3 j=1 2 3 (1)