|
基于近似算法求解多设备差异批调度问题# 程八一* 基金项目：教育部博士点基金（20110111120015） 作者简介：程八一（1981-），男，讲师，主要研究方向为生产运作与供应链. E-mail: chengbayi@yahoo.com （合肥工业大学管理学院，合肥 230009） 摘要：考虑了5 一类作业尺寸有差异的批调度问题，加工环境为并行批处理设备。以制造跨度 为优化目标，建立了基于整数规划的数学模型；分析了制造跨度最小化问题的计算复杂性， 给出问题可行解规模的上下界；然后设计了一种基于LPT 规则和Batch First Fit 规则的近似 算法，证明了算法的时间性能为O(nlogn)，算法在优化制造跨度时的最坏性能比为（8/3 – 2/3m）。 10 关键词：批调度；差异作业；并行设备；近似算法 25 0 引言 差异作业的分批调度问题（Scheduling batch-processing machines with non-identical job sizes, SBN）在实际工业中有着广泛应用，如港口货物装卸、食品加工、半导体芯片预烧、 船闸调度等，这些调度问题兼具古典调度问题和批调度问题的特征，在调度过程中，作业之 间在时间上具有先后约束，在空间上作业需要分批在设备上加工，每一批作业的总尺寸不能 30 超过设备的容量。因此，SBN 问题在传统调度问题上增加了空间维度的约束，其复杂性比这 传统调度问题更高。 目前SBN 的的研究集中在确定型单机问题上（Scheduling single batch-processing machine with non-identical job sizes, SSBN）。采用调度问题的通用表示方法，SSBN 问题可以表示为 1| B, sj, batch| f，其中sj 表示作业J 的尺寸， B 表示设备的最大容量，batch 表明设备为批处 35 理设备，f 为问题的优化目标，目前的研究中，f 主要采用制造跨度和加权完工时间。Uzsoy[1] 提出了SSBN 问题，设计了1| B, sj, batch| Cmax 和| B, sj, batch|ΣCj 两类问题的启发式算法，但 没有对这些算法的近似性能进行分析。后期的研究主要集中在优化方法的设计上， Sung[2] 改进了优化Cmax 的启发式算法；Dupont 和Flipo[3]采用了结合穷举策略的分枝定界法，在一 定程度上提高了算法的求解性能。智能算法在SSBN 的研究中也有较多的应用，Sevaux 和 40 Peres[4]首先引入了遗传算法（Genetic algorithm, GA），对加权延迟作业数进行优化；文献[5]、 [6]基于SSBN 的特征改进了GA 的编码和进化机制，提高了GA 的求解性能。Melouk[7]采用 了模拟退火算法（Simulated Annealing, SA）对Cmax 进行优化，并设计了基于随机产生机制 的基准算例。另外，在SSBN 近似算法的研究方面，也取得了一定的进展。Zhang[8]提出了 作业可分割假定，同时假定大作业数量不超过小作业，在此1| B, sj, batch| Cmax 情形下， 设 计了优化SSBN 的近似算法SR（Split and 45 Rearrange），证明了近似算法的最坏性能比为3/2， 而对于一般情况下的SSBN 问题，提出的MLPT-FF 算法的性能比为7/4；Li[9]分析了作业到 达时间不同的SSBN 问题，即1| rj, B, sj, batch| Cmax，设计了Schedule_Whole 算法，证明算法 的最坏性能比为R = 2 + ε，ε→0；Kashan[10]设计了1| B, sj, batch| Cmax 的近似算法，假定作业 尺寸均匀分布在m 个连续区间内，设计的算法最坏性能比为3/2，渐进性能比为(1 + 1/m)， 50 进一步改进了单台设备问题的求解性能。除了上述SSBN 的离线优化算法研究之外，对在线 问题1| Online, B, sj, batch| Cmax，柏庆国等[11]提出了一种竞争比不大于161/60 的在线算法。 另一方面，模糊环境中的SSBN 问题也已经有相关研究[12], [13]。 但在现实的经济活动中，单台设备问题是相对较少的。例如在芯片制造系统中，预烧炉 为加工设备，芯片为待处理的作业，大部分情况下有多台预烧炉可以并行处理；同样在食品 55 加工中，更常见的是多台设备的并行作业。对并行批处理设备上的差异作业调度问题 （Scheduling parallel batch-processing machines with non- identical job sizes, SPBN），现有的 研究成果极少，所采用的方法均为元启发式算法，包括SA[14]和GA[15]。本文从SPBN 最优 解的性质入手，设计了时间性能为O(nlogn)的有性能保证的启发式算法，以期为SPBN 问题 的求解供更为直接有效的参考。 60 1 问题描述 本文考虑SPBN 的制造跨度的最小化问题，即Pm| B, sj, batch| Cmax。SPBN 问题中，加工 设备的集合为M = {M1, M2…Mm}，设备的最大容量为B；作业集合为J = {J1, J2…Jm}，作业 Jj 的尺寸为sj。设备具有相同的处理能力，在每台设备上，Jj 的处理时间均为pj (j = 1, 2…m)， Mi 上加工的所有批次记为i1 b 、i2 b … iKi b ，其中i K 为i M 上的总批数，而 1 m i i K K = = Σ ， ik b 在i M 上 的处理操作记为ik O ，时间为ik 65 P 。SPBN 上作业的加工过程如下： （1）作业以批为单位在设备上加工，总批数记为K ，任一批( 1,2 ) k b k = 原创学术论文网Tag：代发论文 代写论文 代写代发论文 |
 |
 |
 |
 |
 |
 |
 |
