有顺序约束的单件车间调度问题的逆序算法

《有顺序约束的单件车间调度问题的逆序算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第24卷第6期鞍山钢铁学院学报VO1．24No．62001年12月JournalofAnshanInstituteofI．＆S．Technolog?Dec．，2001有顺序约束的单件车间调度问题的逆序算法李琦，梁斌，王睿智，刘鸿雁(1鞍山钢铁学院电子与信息J：程学院，辽宁鞍山114002；2鞍钢机械制造公司灵th机械厂，辽宁鞍I'【J114033；3．鞍山钢铁学院计算机科学与工程学院，辽宁鞍山114002；4鞍山钢铁学院研究生部，辽宁鞍山114002)摘要：研究了部分工件在加工顺序上存在逻辑优选顺序约束的单件车间调度问题，针对工件之间存在的加工顺序关系，构造了以交货期为基准，以

2、寻求最长加工路径加工时间最短为目标的逆序算法，求解问题，通过实例分析，说明了这一算法在工程中的可行性，关键词：顺序约束；单件车j'g；调度问题；目标函数；逆序算法中图分类号：TP301，6文献标识码：A文章编号：lo0—1654(2001)06—0411—05单件车间(Jop．Shop)调度问题是组合最优化领域的一类重要问题，在生产计划调度、计算机数据处理与存储等方面有广泛的实际背景，在理论上又与算法理论、复杂性理论密切相关，因而备受关注，对于单件车间作业计划问题(JSP)的研究，目前已取得了相应的成果，如分支定界法¨J、遗传算法、神经网络法’、模拟退火法等．这些方法在理论上探

3、索较多，对于小规模的调度效果较好，但对于机器数量和工件数量较多的实际生产调度问题，在计算机上的运行时间很多，工程应用不太理想，本文将讨论这样一类特殊的Job—Shop问题：N个工件经过m台机器加工，其中有部分是组装件，且组装件内部工件在加工顺序上存在逻辑优先顺序约束．对于这种特殊的单件车间调度问题，本文提出一种与逆序启发式调度法相结合的算法，以比较快的速度寻找有一定优度的排序解．1问题描述1．1基本假设现有m台机器．，，⋯，．和n个工件．，：，⋯，其中，：，⋯，是组装件，+，⋯，是n一0个单件．组装件(i=1，2，⋯，0)由n。个工件按一定装配顺序加工装配而成．单件是指单个工件

4、，不需装配，加工后直接交货．因此，不考虑组装工艺，实际工件总数N=a-．an．+n一0．￡=1已知：(1)工件(i=1，2，⋯，Ⅳ)所包含的工序数为Q．加工路线为：)一)一⋯一I(『n)．其中{i(1)．i(2)，⋯，i(m)}为1，2，⋯，m的一种排列．(2)工件(i=1，2，⋯，Ⅳ)的第道工序在机器M上加工时间为P(i，J．，J})，且P(i，，J})≥0．(3)组装件(，，⋯，)和单件(+一，)有交货期，交货期为D(i)(i：1，2，⋯，0，0+1，⋯，n)，且D()≥0．(4)工件的原料到达时间或称准备就绪时间为r(i)(i=1，2，⋯，，v)，这个时间指的是工件原料从

5、外部进入车间，可以开始进行加工的时间．收稿日期：2001—10—30．作者简介：李琦(1974一)，男，湖南芷江人，助教；刘鸿雁(1958一)，女，山西阳泉人，副教授·4l2·鞍山钢铁学院学报第24卷_1．2优先顺序约束组装件由若干工件按一定的加工组装顺序装配而成，在加工过程中存在逻辑优先顺序约束．优先顺序约束是指工件加工顺序上的约束，即哪个工件排在前面加工，哪个工件排后面加工．组装件的组装逻辑关系是树型关系，可以用一棵组装逻辑树(简称组装树)表示．在组装树中，工件与树中的结点一一对应，起始加工工件与树中的叶子结点对应，最终成品与树的根结点对应．例一组装件由。，：，，，，，，。

6、组装成．组装逻辑关系(即组装树)如图l所示．该组装件内部优先顺序约束为：工件：，。必须领先于。加工；工件，，。领先于J；．，。，J，J必须领先于．在该组装树中，工件对应的结点是根结点，工件：，，，，，对应图l组装树的结点是叶子结点．Fig．1Assembling—Tree1．3Job．Shop约束条件对于上述问题需要满足如下条件：(1)一台机器在某一时间内仅加工～个工件；(2)同一个工件在某一时间内仅在一台机器上加工；(3)当一个工件的某道工序一旦开始加工，必须完成，不允许中途停顿；(4)对于每一工件必须在上道工序完成之后，才能进入下道工序；(5)允许工件在工序之间等待，允许机

7、器在工件未到达时闲置；(6)所有机器，原则上可随时开动．1．4目标函数工件(i=l，2，⋯，Ⅳ)原料的到达时间为r(i)；工件的交货期为D(i)．最长加工路径为max{D(i)一r(i)}(1)目标函数f=min{max{D(i)一r(i)}}(2)以交货期D(i)为基准，使最长加工路径加工时问最短来保证加工周期最短．2启发式算法2．1算法的基本思想，以各工件交货期为基准，根据工件加工路线，采用EDD和MWKR两级调度法则逆序排出机台作业计划．EDD法则：最早完工期限法则；MWKR法则：优先