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

控制管理中文核心期刊＜微计算机信息＞（管控一体＇９５）２００８年第２４卷第２－３期

ｍｉｎｒ２∑ｎｌ＝ｋ）１ｆ

其中：

Ａ＝ｆ（Ｈ４

、，

％

１２３４

１

２

３

４

５

６７８９１０

（２）

１

６

Ｔ：所有生产线的总的切换时间，Ｍ：生产线的条数，Ｎ：定单数，Ｓ。：分配在注塑生产线Ｊｋ上生产的定单，Ｈ。：注塑生产线Ｊｋ上定单的加工顺序。Ｈ。可以这样得出：假设ｓｋ上有ｑ个定单｛Ｐ。，Ｐ２，．．．匕

ＰｑＥＱ，ｉ＝ｌ…２一Ｎｌ在注塑生产线Ｊ。上加工，那么可以排列组合出

４

５６７８９ｌＯ

所有的加工顺序（＿一般情况下，一条注塑生产线上安排的定单数不会多余４个．所以排列组合出的所有加工顺序的计算量不会很大），计算每种加工顺序的定单切换总时间氏，从中得到最小

在表中，列代表的是定单号，行代表的是注塑生产线号。＊代表定单不能在此条注塑生产线上生产．因为它选择的注塑生

切换时间的加工顺序７Ｉｋ。设第ｉ种顺序为（Ｐｉ，，％．．蹦，则：

死＝ｔ（Ｐ，１，ｐｎ）＋ｆ（Ｐｊ２，Ｐｆ３）＋…＋ｔ（Ｐｉｑ—Ｉ，＾）

＝ｔ（ｃｆｔ，ｐｉ２）＋ｔ（ｃｊ２，Ｄ３）＋…＋ｆ（ｃｗ—ｌ，Ｃｉｑ）

ｎｍｉｎ＝ｍｉｎ｛ｒ日，ｉ＝ｌ，２，¨．，ｇｌ｝；

产线要满足似，Ｄｊ≥巩Ｊ＝ｌ…２．．Ｍ）。所以它在禁忌表中是无穷大

的，永远都不能选择。表格中的６代表定单２选择注塑生产线３（３）

时为禁忌对象，此时禁忌长度为６。

３）适配值．用Ｔ来表示其适配值。适配值越小代表此种分配方案越好。

”Ｊ

’

把切换时间为１ｋ的加工顺序表示为Ｈｂ在Ｊｋ上加工的

总时间为：

～．

‰：争争伽／％＋Ａ。

。扛１．户：

ｆＴ岫，ｚｋ＜２４ｈ；

。’

４）领域．每个定单选择不同的注塑生产线称为移动，领域为所有这些移动所构成的系列。例如：定单编码为：定单号：ｌ，２，３，４，５，６，７，８，９，１０，编码为：３，４，５，１，１，２，２，３，４，５．定单１在注塑线３上生产，如果定单１选择注塑线２，称为一次移动（其它的定单号选择不变）。这次移动就是当前解的一个领域。

５）藐视准则．如果侯选方案Ｔ值比当前的方案的Ｔ值小。但它是被禁忌的。则把它解禁出来。

６）终止准则．给定一个很大的迭代步数，如果总的迭代步数一超过它，算法就停此搜索。迭代的步数与安排的定单数多少有关。

７）禁忌长度．禁忌长度由定单的规模确定。２．４算法流程图。

那么Ａ＝厂（胁）表示为Ａ２｛Ｚ≥；而

２１３算法步骤调度分为两个步骤：

（５）

第一步：利用禁忌搜索算法，把所有定单的第一天的交货量

ｎｉｌ（ｎ—ｏ，ｉ＝１…２¨，Ⅳ）安排到注塑生产线上。

第二步：在第一天的定单数量全部安排之后。可以知道每一条注塑生产线Ｌ的最后一个加工的定单编号ｂｉ，这里有以下几种情况：

１）注塑生产线凡已经安排满Ｔ（２４小时），这条生产线安排结束：

２）注塑生产线Ｊ。没有安排满，那么看定单ｂｉ的交货表是否还有要交货的数量，如果有继续安排，直到安排满。如果ｂｉ剩余的交货数量都不能安排满这条生产线，那么在交货表里找一个还有交货数量的．并且和ｂ；的颜色切换时间最小的定单安排上去，直到安排满。

２．３ｌ禁忌搜索算法

禁忌搜索算法是由Ｇｌｏｖｅｒ在１９８６年提出的，其基本的思想是：给定一个初始解和一个临域，然后在当前鳃的临域中确定若干候选解：若最佳候选解对应的目标值优于当前最优解状态，则忽视其禁忌特性，用其代表当前解和最优解状态，并将相应的对象加入禁忌表（用于记录候选解禁忌属性的表），同时修改禁忌表中各对象的任期；若不存在上述候选解，则在候选解中选择未被禁忌的最佳状态为新的当前解．而无视它与当前解的优劣，同时将相应的对象加入禁忌表．并修改禁忌表中个对象的任期；如此重复上述搜索过程直至满足停止准则。在本文中，禁忌搜索算法的各项参数如下：

１）解的编码。解的编码淑膨ｔ，膨ｚ，膨，，．．．蟛。膨¨…，膨ｖ），膨是指注塑机的编号，总共有Ｎ个定单。膨可以等于膨＋－。例：假设

有１０个定单，５条注塑生产线，这定单编码为：定单号：ｌ，２，３，４，５，６，７，８，９，１０编码为：３，４，５，１，１，２，２，３，４，５。编码表示为：１号定单安排在注塑线３上，２安排在注塑线４上，依次类推。

２）禁忌对象，禁忌表。禁忌对象为ＴＡｉｉ＝（ｏ；Ｊｊ＇ｘ）ｉ＝ｌ…２．．，Ｎｉｊ＝

ｌ，２，．．．Ｍ；表示为定单ｉ不能选择注塑生产线ｊ，禁忌的大小为ｘ。

壹

Ｓｋ：第ｋ条注塑线上的定单

Ｏｋ：第ｋ条注塑线上的定单加工顺序

禁忌表为一个矩正ＴＡ＝［Ｘｒａ门，例：禁忌表的形式如下所示：

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

丌转第１８页）