基于禁忌搜索算法的生产调度

控制管理

文章编号：１００８－０５７０（２００８）０２－３—∞５５－０２

基于禁忌搜索算法的生产调度

ＰＲＯＤＵＣＴｌ０ＮＳＣＨＥＤＵＬＥＢＡＳＥＤＯＮＴＡＢＵＳＥＡＲＣＨＡＬＧＯＲｌＴＨＭＳ

（广东工业大学）刘忠耀彭重嘉伍乃骐

ＬｌＵＺＨＯＮＧＹＡＯ

ＰＥＮＧＣＨＯＮＧＪＩＡ

ＷＵＮＡＩＱＩ

摘要：基于启发式规则和禁忌搜索技术，提出了一种即要优先满足定单交货期，而且使得注塑生产线上的总的定单切换时间最小化的生产调度的算法，通过计算机的模拟仿真，证明此算法的有效性。关键词：生产调度；禁忌搜索算法；启发式规则中图分类号：ＴＥ

３０１

文献标识码：Ａ

Ａｂｓｔｒａｃｔ：Ａ

ｐｒｏｄｕｃｔｉｏｎｓｃｈｅｄｕｌｅａｌｇｏｒｉｔｈｍ

ｗａｓ

ｐｒｅｓｅｎｔｅｄｂａｓｅｄｏｎｈｅｕｒｉｓｔｉｃｓａｎｄｔａｂｕｓｅａｒｃｈａｌｇｏｒｉｔｈｍｓ，ｗｈｉｃｈｃａｎｎｏｔｏｎｌｙｐｒｉｏｒｉｔｙｓａｔｉｓｆｙｔｈｅｏｒｄｅｒ’Ｓｄｅｌｉｖｅｒｄａｔｅ，ｂｕｔａｌｓｏ

ｃａｎ

ｍａｋｅｔｈｅｔｏｔａｌｏｒｄｅｒ’Ｓｓｗｉｔｃｈｔｉｍｅｍｉｎｉｍｕｍｉｎｔｈｅｉｎｊｅｃｔｉｏｎｐｒｏｄｕｃｔｉｏｎｌｉｎｅ．Ｔｈｒｏｕｇｈ

ｔｈｅｓｉｍｕｌａｔｉｏｎｉｎ

ｃｏｍｐｕｔｅｒ，ｉｔｃｏｎｆｉｒｍｅｄｔｈｅａｌｇｏｒｉｔｈｍ

ｗａｓ

ｅｆｆｅｃｔｉｖｅ．

Ｋｅｙｗｏｒｄｓ：ＰｒｏｄｕｃｔｉｏｎＳｃｈｅｄｕｌｅ，ＴａｂｕＳｅａｒｃｈＡｌｇｏｒｉｔｈｍｓ，ＨｅｕｒｉｓｔｉｃｓＡｌｇｏｒｉｔｈｍｓ

１引言

例：某注塑厂定单交货计划表形式如下表所示。

定

吨数颜色需求产能

四

五七

生产调度问题一直是研究的热点问题，它对于降低生产成堕

数

本。缩短制造周期，提高生产效率具有重要的意义。由于制造系００１ｌ∞ｔ

白踟００３（１ｌｅａ／ｈ１０００

１０∞１０００２０００２咖

１∞０

０统千差万别，特点各不相同．所以所采用的生产调度模型调度００２撇

红

１００００２００ｅａ／ｈ３０∞

１０００

０２０００１０∞

１０∞２０００∞Ｂ

３００ｔ

手段也是不同的。注塑生产是一种混合型的生产过程，一般是　黑

１５０００

４００ｅａｒｎ

３０００

３０∞０

Ｏ

３∞０

４０００

２０００

面向订单生产，产品品种变化比较大，批量相对小。同时，注塑在表中．每个定单的需求数等于后面７天要交货数的总机台数多，每一注塑机又生产不同的产品，批量相对又比较大，和。０代表这一天不用交货。

所以注塑生产线上的调度是比较复杂的。注塑企业是按定单生一般注塑厂有几十条到上百条注塑生产线。每条注塑生产产．按期交货是极其重要的，所以这又给注塑生产线的调度提线都有一个吨位参数，只有吨位参数小于注塑线上的吨位参数出了更高的要求。

的定单可以在此条生产线上生产。注塑生产线上进行不同定单考虑到每条注塑生产线不同产品进行切换时要考虑到洗的切换时，要考虑到定单的颜色问题。由于不同颜色的定单进机问题（洗机时间由颜色的差异来决定），而对注塑生产线排产行切换时，注塑生产线要进行洗机。颜色相同的的定单不用洗时还要考虑吨位参数要求，加上前面所述要求，使得以往注塑机，颜色相近的定单洗机时间少，颜色相差较远的定单洗机时企业的生产调度都是由人工按经验进行，这样柔性比较好，比间较长。这就影响定单切换的时间。两个不同的定单的切换时较灵活，但是随着规模的不断扩大。人工经验排产已经越来越Ｉ可为：ｆ（ｏ，Ｏｊ）＝ｔ（ｃｉ，ｃｊ）ｆ，，＝１，２，．．．Ｎ，ｉ≠，；

不能满足生产的要求。效率越来越低下，生产成本很高。而到目２．２调度模型的建立前为此．并没有相关的关于注塑生产线的生产调度系统的研对调度模型的假设：

究。本文的研究就是要解决该领域的问题，填补其空白。

１．每个定单只能在一条注塑线上生产。２生产过程的的描述

２．加工每个定单批量过程中，不能中断。

根据注塑生产线吨位的要求，定单０ｉ在选择注塑生产线加２．１生产过程的的描述

工时必须首先要满足所选择的注塑生产线吨数参数要不小于注塑厂一般按定单生产，每个定单按批交货。设有Ｎ此定单的吨位要求，所以可以加工０。的注塑生产线有：

个定单Ｄ＝｛（６ｔ，ｄ，ｃｆ，ｇｉ，Ｖｉ，ｗ，），ｉ＝１，２，．．．Ⅳ｝，在Ｍ条注塑生产线

｛巧，历≥办，Ｊ＝ｌ…２．．Ｍ｝，所以根据这个条件．可以限定定单可以

巧＝（（蟛，历），＿，＝ｌ…２．．Ｍ｝上生产。定单交货计划为ｗｉ＝（ｎ。ｎ。．ｎＪ，在那些注塑生产线来安排生产。按定单的吨数从大到小排列。ｉ＝ｌ…２．．Ｎ，需求总数ｎ＝∑％ｉ＝ｌ…２一Ｎ；其中：

可以知道定单依次对应那些注塑生产线。

０。：第个定单ｉｉ：第ｊ条注塑生产线ｂ，：定单编号ｄｉ：定单吨例：假设有５个定单（０。５００吨），（０≯５０吨），（０，４５０吨），（０。位要求Ｃ。：定单颜色ｒｉ：定单需求总数Ｖｉ：定单产能砜：第ｉ个定４００吨），（ｏ，，３００吨），（ｏ白１００吨）。有４条注塑生产线：（Ｊ。５００吨），（Ｊ２，

单的第ｔ天的交货量ｗ；：定单交货计划Ｍ；：注塑生产线编号４００吨），‰３００吨），（Ｊ口００吨）。所以定单和注塑生产线有一个对

Ｄ；：注塑生产线的吨位参数

应关系｛Ｄｌ，Ｊｔ｝，（Ｄ２，Ｊ１），｛Ｄ３，Ｊｉ｝，｛０４，（Ｊｌ，．，２）｝，｛０５，（．，ｌ，Ｊ２，＾）｝，｛０６，（Ｊｒ，Ｊ２，Ｊ３，＾））。

刘忠耀：在读硕士研究生

调度的首要目标满足订单的交货期，其次是定单在生产线上切换时间尽可能少。目标函数为：

Ａ控ｌｌｌ邮局订阅号：８２－９４６３６０元，年一５５—