一种新型的作业车间调度算法的研究与实现
第２３卷第１０期２００４年１０月
机械科学与技术
ＭＥＣＨＡＮｌＣＡＬＳＣＩＥＮＣＥＡＮＤ’ＩＥＣＨＮＯＬＯＧＹ
Ｖ０１．２３Ｎｏ．１０
０ｃｔｏｂｅｒ２００４
王龙生文章编号：１００３－８７２８（２００４）ｌＯ－１１８１ＪＤ４
一种新型的作业车间调度算法的研究与实现
王龙生，叶文华
（南京航空航天大学ｃ１Ｍｓ工程研究中心，南京２１００１６）
摘要：将工件的剩余加工时间分为相对剩余加工时间和绝对剩余加工时间，提出了优先分配启发式算法的一种新的优先分配规则，即相对剩余加工时间最大的概念，把调度分成多个阶段的部分调度，通过比较部分调度集合中的可调度工序的相对剩余加工时间，求解出每个部分调度的最优解，从而使整个调度达到全局最优或近似最优。最后，开发出调度软件，验证了算法在工程中的可行性、有效性。
关键词：车间调度；分配规则；启发式算法
中图分类号：’】鸸Ｏ文献标识码：Ａ
ＡＮ洲Ａｐｐ瑚ｃＩＩｆ；时ＪｏｂＳｈｏｐＳｄｌｅｄｌｌｌｉｎｇＰｒｏｂＩ咖
ＷＡＮＧＬｏｎｇ—ｓｈｅｎｇ，ＹＥＷｅｎ－ｈｕａ
（ＲｅｓｅａｒｃｈＣｅｎｔｅｒｏｆＣＩＭＳＥｎ舀ｎｅｅｒｉｎｇ，
ＮａｎｊｉｎｇＵｎｉＶｅｒｓｉｔｙｏｆＡｅｒｏｎａｕｔｉｃｓ＆Ａｓｔｒｏｎａｕｔｉｃｓ，Ｎ姐ｊｉｎｇ２１００１６）
Ａｂｓ虹舵ｔ：Ｗｅｐｒｅｓｅｎｔａｎｅｗ叩ｐｒｏａｃｈｏｆｊｏｂｓｈｏｐｓｃｈｅｄｕｌｉｎｇｂａｓｅｄｏｎａｎｅｗｈｅｕｒｉｓｔｉｃｄｉｓｐａｔｃｈｉｎｇａｌｇｏ—ｄｔｌｌｍ．１ｎｔｈｉｓａｐｐｒ０８ｃｈ，ｒｅｍａｉｎｉｎｇ叩ｅｍ￡ｉｎｇｔｉｍｅ（ＲＯＴ）ｉｓｄｉＶｉｄｅｄｉｎｔｏ￡ｗｏｔｙｐｅｓ：ｏｎｅｉｓｃ伽ｐａｒａｔｉＶｅＲＯＴ，ａＩｌｄｔｌｌｅｏｔｌｌｅｒｉ８ａｂｓｏｌｕｔｅＲＯＴ．Ａｎｅｗｄｉｓｐａｔｃｈｉｎｇｍｌｅ—ｂｉｇｇｅｓｔｐａｎｓ’ｃｏｎｌｐａｒａｔｉＶｅＲＯＴｆｉｒｓｔ，ｉｓｐｒｅ∞ｎｆｅｄ．Ｔｈｅｗｈｏｌｅｓｃｈｅｔｌｕｌｉｎｇｃｏｎｓｉｓｔｓｏ量－ｍａｎｙｓｔａｇｅｓｏｆｐａｒｔｉａｌｓｃｈｅｄｕｌｉｎｇ．Ｉｎｔｌｌｅｐ枷ａｌｓｃｈｅｄｕｌｉｎｇ，ｔＩｌｒｏｕｇｈｃｏｍｐａｒｉｎｇｓｃｈｅｄｕＩａｂｌｅｃｏｍｐｅｔｉｔｉＶｅｐ８ｎｓ７ａｂｓｏ王ｕ【ｅＲＯＴｗｉｔ｝ｌｃｏｍｐａｒａｔｉｖｅＲｏＴ，ｔ｝ｌｅｐａｒｔｗｉｔＩｌｂｉｇ—ｇｅｓｔｃｏｍｐａｒａｔｉＶｅＲＯＴ
ｉｓｆｉｒｓｔｐｒｏｃｅｓｓｅｄ锄ｏｎｇｃｏｍｐｅｔｉｔｉＶｅｐａｒｔｓ，ｓｏａｓａｔｉｓｆａｃｔｏｒｙｓｃｈｅｄｕｌｉｎｇ∞ｌｕｔｉｏｎｉｓ
ｏｂｔａｉｎｅｄ．ＡｔｄＩｅｅｎｄｏｆｓｃｈｅｄｕｌｉｎｇ，ａｌｌ
ｐａｎｉａｌｓｃｈｅｄｕｌｉｎｇｓｅｔｓｅｓｔ＆ｂｌｉｓｈｏｐｔｉｍａｌＳｃｈｅｄｕｌｉｎｇ∞ｑｕｅｎｃｅ．ｎｉｓｓｃｈｅｄｕｌｉｎｇａｌ鲥出ｍｉｓｐｍｖｅｄｔｏｂｅｅ艉ｃｔｉＶｅｂｙｅｘ锄ｐｌｅｓａｎｄｔ｝ＩｅｏｒｙａＩｌａｌｙｓｉｓ．
Ｋｅｙｗｏｒｄｓ：Ｊｏｂ—ｓｈｏｐｓｃｈｅｄｕｌｉｎｇ；Ｄｉｓｐａｔｃｈｉｎｇ１１ｌｌｅ；Ｈｅｕｒｉｓｔｉｃａ１９０ｒｉｔｈｍ
作业车间调度（ＪＳＰ）广泛应用于实际生产，是生产管理系统中的一个关键环节。生产调度问题是一种比较典型的组合优化问题，而且大部分是ＮＰ．ＨＡＲＤ问题。
单件、小批量、多品种是目前许多工厂采用的生产方式，丽单件车间调度（Ｊｏｐ－ｓｈ叩）是一个具有代表性的生产调度问题。对于单件车间调度问题，目前的研究成果较多，例如分支定界法、启发式方法【ｌＪ、神经网络方法拉。以及遗传算法口１等，这些方法在理论上的探索较多。多数算法由于计算复杂，只适用于规模较小的作业车间调度问题。由于单件车间调度问题的复杂性，对于机器数量和工件数量均较多的调度问题，上述算法在计算机上的运行时间较长，工程中应用不太理想。
许多研究表明，寻找ＪｓＰ的最优解非常困难，最有工程意义的求解算法是放弃寻找最优解的目标，转而试图在合
收稿日期：２００３一０９一０３
作者简介：王龙生（１９７６一），男（汉）．江苏，硕士研究生
∑－ｍａｉｌ：ｎｊｗｌ８＠１６３．ｃｏｎｌ理、有限的时间内寻找到一个近似的、有用的解。由于优先分配启发式具有容易实现和较小的时间复杂性，因而是实际求解调度问题经常使用的方法。对于一个给定的部分调度，算法主要是识别所有的加工冲突，即竞争同一机器的工序，尔后在每一阶段采取一些步骤以多种可能的方式解决这些冲突。而启发式则用优先分配规则选择工序来解决这些冲突。可以看出算法的关键是选择好优先分配规则，本文根据实际生产情况，提出了相对剩余加工时间的概念，将相对剩余加工时间最大作为分配规则。
ｌ调度问题的描述
作业车间调度问题可以表述为：有ｍ台不同的机器和ｎ个不同的工件，每个工件包含一个由多道工序组成的工序集合，工件的工序顺序是预先给定的，每道工序用它所要求的机器和固定的加工时间来表示。此外对工件和机器约
束有： 万方数据