姚远远 叶春明

上海理工大学管理学院，上海，200093

0 引言

薄膜晶体管液晶显示器(thin-film transistor-liquid crystal display，TFT-LCD)的制造过程主要包括三个阶段：TFT阵列/彩色滤光制程、液晶成盒、模块组装制程[1]。为了减少在制品数量、缩短生产周期，企业通常在阵列制程的每个工位放置多台并行机器。TFT-LCD面板阵列制程的生产过程可归结为可重入混合流水车间(reentrant hybrid flow shop，RHFS)问题，即所有工件在各工位之间具有相同的加工路径，并按照相同的加工顺序重复多次，且至少有一个工位有多台机器。RHFS调度问题是经典的混合流水车间调度与可重入调度的合成体，已被证明是NP难题[2]，不能用传统的数学模型方法求解，因此，开发针对该问题的高效智能优化算法研究是车间调度领域的热点，具有重要的理论意义和实用价值。

CHOI等[3]将TFT-LCD制造简化为两阶段的RHFS调度问题并构建数学模型，以满足最大允许交货期的条件下使最大完工时间最短为调度目标，提出一种分枝定界算法和三种改进的启发式算法(Johnson、CDS和NEH)进行求解。CHOI等[4]研究了需要同时满足系统产出最大，平均运行时间、平均延误时间、总误工工件数最小的多个优化目标的实时动态RHFS调度问题，采用一种基于决策树的实时调度机制来选择合适的调度规则，并将其成功用于实际的TFT-LCD面板生产线。DUGARDIN等[5]提出了一种基于Lorenz支配的多目标遗传算法，求解了以最大化瓶颈机器利用率、最小化最大完工时间为目标的RHFS问题。为求解优化目标是最小化最大完工时间和总拖期时间的RHFS调度问题，CHO等[6]提出了Pareto遗传算法，YING等[7]提出了迭代Pareto贪婪算法，SHEN等[8-9]提出了改进教与学优化算法、基于Pareto的离散和声搜索算法。……