含不同投放时间和重量的单熔炼炉批调度优化

模具精铸方法不仅可以快速精铸出-定批量的模具 ，而且也能克服传统方法对-些独特造型加工困难的问题 ，可有效地提高模具制造效率和模具制造质量，在模具制造中获得了越来越多的应用。模具精铸制造中，需要使用熔炼炉对铝合金进行熔炼。铝合金熔炼是-个高耗能过程，同时由于熔炼炉数量有限，往往会成为精铸的瓶颈。因此对铝合金熔炼任务合理组批调度，对于企业节能减排、降低成本、提高模具制造效率具有重要意义。

本文针对单熔炼炉批调度进行研究 ，由于不同熔炼任务需要的铝合金熔炼重量不-样，且熔炼任务时间往往不相同，因而铝合金熔炼过程可以看成是-个具有不同任务到达时间和不-致任收稿日期：2013-07-16务尺寸 (或重量)的任务单机批调度问题u ，即1 Sj，BIC 问题。不-致任务尺寸单机批调度问题是-类典型的分批排序问题。-般分批排序主要有三种模型：批工时为该批中最大工件工时的并行批 (paralel batch)、批工时为该批中各工件工时之和的串行批 (serial batch)及批工时为常数的模型忙 。目前针对不-致任务尺寸批调度问题的研究 ，大都基于并行批模型，假设批工时为批中最大任务工时。

Uzsoyp 针对并行批，不考虑任务的到达时间，首先提出了不-致尺寸任务单机批调度问题，证明了其最携总完工时间∑ 及最携最大完工时间C 问题均为NP-hard，并提出了批首次匹配规则 (Batch First Fit，BFF)等启发式算法进行求解。BFF规则是在随机排列的任务中，孟 超 等：含不同投放时间和重量的单熔炼炉批调度优化从第-个任务开始依次挑选任务，并将该任务分配到可以容纳该任务的第-个批中；如果没有批可以容纳该任务，则创建新批接纳该任务p 。针对不考虑任务到达时间的不-致尺寸任务单批处理机调度 的最携最 大完工时间 问题 ，即 ：llsf，BIC 问题 ，文献 -7提出了不同的智能算法，这些算法通常采用任务序列作为个体，产生随机任务序列后，采用BFF规则分批求目标值。

针 对 1 sj，BIC 。 问 题 ，文 献 8提 出 了- 种merge-split规则改进BFF启发式规则的分批结果，并与遗传算法相结合，提出了-种混合遗传算法对问题进行求解 ；文献[9]提出了-种蚁群算法，引入了浪费-空闲空间比概念，并基于此设计了动态的启发式信息以更精确地指导蚂蚁的行为，同时，引入候选列表策略，有效地减少了蚂蚁的寻优空间。

尽管关于批调度研究的文献较多，但是大多文献都基于并行批进行研究。然而，对于模具精铸铝合金熔炼而言，熔炼批工时既不是该批中最大任务工时，也不是该批中各任务工时之和，更不是常数，而是与熔炼铝合金重量为单调递增函数关系n，为简化研究，本文设熔炼批工时与熔炼重量为线性函数关系。本文结合模具精铸过程中铝合金熔炼实际情况，研究含不同投放时间和重量的单熔炼炉批调度优化，并根据熔炼批工时的特点，安排熔炼任务合理组批，最携熔炼任务最大完工时间。

1问题描述与数学模型设只有-台熔炼炉 ，有 凡个铝合金熔炼任务，熔炼任务 ∈，1，，nJ。已知每个熔炼任务需熔炼的铝合金重量 f及投放时间 0，熔炼炉的熔炼能力 C；熔炼时间 p 分为固定时间0和可变时间 t ，其中固定时间为熔炼准备时间，熔炼炉的可变时间系数为 卢，则可变时间 t 卢Sj。

优化 目标为最携最大完工时间 C ，该问题用三参数表示法可表示为：1 Sj，NC 。

为便于研究，作以下假设：(1)各任务所需熔炼合金成分相同，可在-台熔炼炉上组批熔炼；(2)任务重量不同，且投放时间不同；(3)每个任务只属于-个批；(4)任务批-旦在熔炼炉上进行加工 ，不允许中断，也不能增加新的任务 ；(5)熔炼加工时间分为固定时间和可变时间，可变时间与熔炼铝合金重量成正比；(6)每批任务的总量不能超过熔炼炉加工能力；(7)不考虑批与批之间的转换时间。

为了便于描述问题，作以下符号说明：k为分批数量；B为分批集合；b为任务批序号，b EB；任务批b需要熔炼的铝合金重量为S ，批投放时间、开工时间、加工时间、完工时间分别为 、t 、P 、e ；决策变量 表示任务 是否属于任务批 b。

根据以上假设，可建立问题如下数学模型：mlnC (1)S.t。

∑ ：1 ∈， (2)s6∑%sj≤c b EBJ EJmiaJx rj) b∈B 6 6∈P6ts s6 b EBe66p6 b∈Bk≤n： b ∈B(3)(4)(5)(6)(7)(8)(9)其中，式 (1)为优化目标表达式，表示优化目标为最携最大完工时间；式 (2)表示每个任务. 邑且只能被分配到-个任务批次 b里面；式(3)表示每-批任务重量为批内各任务重量之和，小于熔炼炉熔炼能力 ；式 (4)、(5)、(6)、(7)表示批的投放时间、开工时间、加工时间、完工 时间；式 (8)表示批 的数量的范围 ；式(9)是决策变量。

2混合模拟退火算法借鉴并行批的单机批调度问题的-般求解思路是：首先对任务进行排序，然后对排序后的任务进行分批，最后将获得的批在机器上进行排序，本文提出了-种混合模拟退火算法 (Hybridsimulated annealing algorithm，HSA算法)。HAS算法流程如图l所示。

业信息化是图1 HSA混合遗传算法流程图ISA算法说明如下。

(1)编码。采用顺序编码方法随机生成任务序列作为个体。

(3)批排序。根据文献10]可知：对于-个单机批处理机，在得到任务分批后，使用最早投放时间优先 (Earliest Release Time，ERT)规则进行排序，可获得当前分批下最携最大完工时间问题的最优解。因此采用ERT规则对批排序。

(4)模拟退火操作。随机产生-个新解，利用Metropolis法则判断是否接受新解▲而找出当前温度下的最优解〉温后，继续寻找新温度下的最优解。