作业车间调度问题的求解算法研究

《作业车间调度问题的求解算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、·华中科技大学硕士学位论文1绪论本章首先阐述课题的选题背景以及该课题对学术研究、实际应用的重要意义，然后叙述作业车间调度问题的模型以及常用的表示方法，并讨论国内外关于该问题的研究发展以及最新研究状况，最后给出本文研究的主要内容以及论文结构安排。1.1选题背景以及课题研究意义随着科学技术的发展以及相关学科之间的不断渗透交叉，组合优化问题越来越广泛地出现在各个行业领域之中，如：工业车间生产制造、交通运输、生物学、光网络流量疏导、无线网络频率分配以及机场航班调度等等。与此同时，如何高效求解由现实生活中的组合优化问题抽象出来的问题模型也成为学术界的研究热点，如：图染色问题，旅行商问题，

2、复杂网络社区发现问题以及SAT可满足性问题等等[1]。本文所研究的作业车间调度问题即属于组合优化领域的研究热点问题。自上世纪50年代开始，调度问题因其自身的广泛性和实用性，开始引起人们的关注并被引入到学术研究中[2][3]。作业车间调度问题很早就已经被证明为属于NP-Hard类的问题，学术工作者为解决这个经典的NP-Hard问题已经付出了半个多世纪的努力，而现在最先进的算法仅限于能够有效地求解较小规模的问题，对于大规模以及超大规模的车间调度问题，至今仍然没有有效的方法能够快速找到其最优解[3]。此外，研究作业车间调度问题的求解算法，对于回答“P是否等于NP”这一问题也同样具有重

3、要的意义[4]。因此，对作业车间调度问题的深入研究具有重要的理论意义。研究作业车间调度问题对于实际应用也具有非常重要的意义。除了排序因素，调度类问题还要考虑任务的起止时间、属性约束等，这一类问题广泛出现在通信网络、医疗卫生、物流运输以及车间制造等领域。作业车间调度是调度类问题最基本的模型，研究该问题有助于解决实际应用中的调度难题、提高人类社会的生产效率。1.2问题描述以及模型表示方法概述1.2.1作业车间调度问题的描述1959年，Bowman首先提出了作业车间调度问题[5]。该问题可以描述如下：给定n个工件，每个工件的加工过程分为若干道工序，每道加工工序必须在给定的m台1···

4、华中科技大学硕士学位论文机器中的一台上加工并且需要的加工时间已知，每一台机器在某个时刻只能加工一道工序，而每道工序必须在工件前续工序加工完成后才能开始加工，在满足这些约束的条件下，给出每道工序的开始加工时刻，使得从第一个开始加工工序的开始时刻到最后一个完成加工工序的完成时刻的这个时间段的长度（makespan）尽可能的短[6][7]。作业车间调度问题属于任务配置以及顺序约束的资源分配类问题。1.1作业车间调度问题的模型表示作业车间调度问题有多种模型表示方法，比较常用的有线性规划模型、甘特图模型以及析取图模型等等。本小节将概述线性规划模型以及甘特图模型的表示方法，析取图模型将在第

5、3章中描述。(1)线性规划模型给定一个具有n个待加工工件以及m台加工机器的作业车间调度问题，以下约束条件必须满足：○1每个工件在机器上的加工次序给定；○2每台机器在任何时刻最多只能加工一个工序。Adams以及Balas给出了作业车间调度问题的线性规划模型[8]，具体描述如下。定义工件集合：J=J；定义机器集合：M={M,}；定义{,11工序集合：O={0,1,,o,o+1}，其中，工序0和工序o+1表示虚拟的“开始工序”和“结束工序”，它们的加工时间都为0。定义集合A为约束条件○1所限制的优先关系工序对儿的集合；定义集合V（kk=1,2,……,m）为在机器Mk上加工的工序集合，

6、集合Ek为在机器Mk上加工的约束工序对儿的集合，EÌV´V，因此要满足约束条件○2。kkk定义di和ti(iÎO)分别为工序i的加工时间和开始加工时刻，那么作业车间调度问题可以描述为：目标函数minto+1约束条件ttd-³jii(i,jA)<>Ît–tdttd(i,jE,MM)³Ú-³<>ÎÎjiiijjkk···t0(iO)³Îi任何满足上述约束的一组ti（i=0,1,……,o+1）都是一个合法的调度方案，问题的目2···华中科技大学硕士学位论文标就是找出一种使to+1尽可能小的调度方案。线性规划模型使用数学表达式将作业车间调度问题的约束条件以及目标函数表示出来，但是过于抽

7、象，不够直观，很难理解其中的具体操作细节，因此，问题模型的图形化表示方法被提出来。(2)甘特图模型甘特图是一种显示项目活动与时间关系的条状图，其思想是，以图示的方式将项目活动的顺序以及活动的持续时间展示出来。表1.1一个作业调度实例工序工件12341M1M3M2M12M2M33M3M14M1M3M15M3M1M2M1表1.1给出了一个简单的作业调度问题[7]，涉及5个工件，3台机器，各工序的加工时间为1。如表所示：a.工件1有四道工序，依次分别在机器M1、M3、M2和M1上加工；b.工件2有