1、第 卷第期计算机集成制造系统 年月 ：收稿日期：；修订日期：。；基金项目：国家自然科学基金资助项目（）；中国博士后科学基金资助项目（）。：，（），（）考虑工件释放时间和柔性维护的单机调度问题李小林，司佳佳，尹传传，李玉鹏（中国矿业大学 矿业工程学院，江苏徐州 ）摘要：针对晶圆制造过程中考虑清洗维护的生产调度联合优化问题，以最小化最大完工时间为求解目标，优化工件加工顺序及维护活动执行时间。证明了该问题为 难的，建立了问题的整数规划模型并进行线性化。结合机器役龄约束下的成批调度问题特征，证明了解的性质，并设计 启发式算法对问题进行求解。构建了考虑工件释放时间及清洁活动约束的下界算法。通过不同规模算
2、例仿真实验，将所提启发式算法与 及下界算法求解结果进行比较，验证了所提算法的有效性。关键词：单机调度；晶圆清洗；柔性维护；释放时间；启发式算法中图分类号：文献标识码：，（，）：，（），：；引言在企业实际生产中，由于设备维护、维修、套件更换、设备或物料清洁等原因，工件加工过程需要中断，在调度过程中可以看作设备并非连续可用。例如在半导体芯片制造的晶圆加工过程中，晶圆表面会累积有机物、金属离子等污染物，为了避免损伤晶圆表面，必须进行清洁才能执行后续加工。在清洁晶圆表面时，需要使用清洁剂溶解污染物，在清洁一定量污染物后，需要及时更换清洁剂以防损伤晶圆，此时设备处于不可用状态。由于清洁剂的清洁效果与其清
3、洁的晶圆累计污染量有关，而且多工序加工使工件具有动态到达的特征，研究这类生产调度与设备预防性维护的联合优化问题在生产中具有重要的现实意义。近年来，生产和预防性维护联合优化问题受到计算机集成制造系统第 卷越来越多学者的关注，预防性维护在实际工业生产中的有效性已被证明。在实际生产背景下，生产调度与设备预防性维护二者密切相关，都会影响设备的可用性和可靠性。机器在连续工作一段时间后需要维护，因此生产调度与设备维护过程并非相互独立，更多情况下会相互影响，良好的调度与维护联合优化可以有效提高设备可用性，降低生产成本。为使工件加工和预防性维护有效结合，通常将维护活动作为一种资源约束引入调度模型。已有生产调度
4、与设备维护相结合的文献中，根据维护的开始时间是否具有柔性，分为固定周期与柔性周期两类不同的维 护 约 束 模 式。对 于 固 定 周 期 维 护 约 束，等以最小化最大延迟为优化目标，提出一种分支定界算法求解该问题，同时针对大规模问题设计了一种启发式算法；以最小化工件完工时间之和为目标，证明了该问题为 难的，并提出种启发式算法和分支定界算法对该问题进行求解；等提出一种基于改进的下界和启发式算法的分支定界算法。对于柔性周期维护，等首次提出机器的不可用区间是不固定的，证明了该问题的复杂度，同时分别以最小化最大完工时间和最小化工件完工时间之和为优化目标，给出相应的启发式算法；等以最小化加权总完工时间
5、和最小化最大延迟为优化目标，对工件可恢复的情况进行研究；张丽华等分别研究了工件可恢复和不可恢复的情况，建立了数学模型，并提出相应的启发式算法；等以最小化最大完工时间为优化目标，提出多种启发式算法求解该问题，并对不同启发式算法的效果进行了比较；等以最小化最大完工时间为优化目标，分别提出一种启发式算法和分支定界算法解决该问题；吴慧等 以最小化所有工件的完成时间之和为优化目标，分别从固定周期预防性维护约束和柔性周期预防性维护两个方面进行研究，建立了整数规划模型，并根据所提最优解性质设计分支定界算法对问题进行求解；甘婕等 以调度作业的总加权期望完成时间最小为目标，引入丝锥性能可靠度约束，进行单机调度与
6、丝锥视情预防性更换的集成建模研究。对于同时考虑固定和柔性周期预防性维护的单机调度问题，王昕等 以最小化最大拖期成本和维护成本为目标建立模型，通过数值实验和调参分析确定了维护决策的关键和非关键因素。对于考虑清洁约束的研究，等 以最小化工件完工时间的总绝对偏差为优化目标，提出一种启发式算法；等 和 等 以最小化工件完工时间之和为优化目标，分别提出相应的启发式算法求解该问题。以上考虑清洁约束的研究只考虑了工件在零时刻同时到达的情况，在实际生产中，由于加工计划和加工时间不确定，柔性维护策略下工件动态到达的情况更为常见，在集成建模中需要考虑符合实际生产的特征进行联合策略研究。本文在考虑清洁约束的同时考虑
7、工件动态到达的情况，以最小化完工时间为优化目标，建立生产调度与柔性预防性维护的联合优化数学模型，并提出有效的启发式算法和下界对问题进行求解。问题描述及数学模型将个工件集，安排在一台机器上加工，（，）分别为工件的加工时间、污染量和释放时间，均为确定已知参数；在忽略空闲时间的情况下，当累计污染量（下文简称机器的役龄）达到时，机器必须停止工作执行一次时长为的清洁活动；假设，（否则无可行方案），且工件不可恢复，即工件一旦开始加工就必须至加工完成才可停止；以最小化完工时间为优化目标，需要对各工件在机器上的加工顺序和执行清洁活动的开始时间做出决策。柔性周期清洁活动约束下的单机周度甘特图如图所示，调度包括在
8、序列中插入的工件序列和清洁活动。一个清洁周期内的所有工件集合看作一个批次，调度序列可以表示为，其中：是中的第个批；为调度中第个清洁活动；是中 机器 的 役 龄，且。根 据 等 提出的三参数表示法，本文问题可表示为，其中：表示单机环境；为工件 的 释 放 时 间；表 示 工 件 不 可 恢 复；表示清洁活动；为目标函数。本文问题的相关参数符号如下：为在第个位置加工的工件；第期李小林 等：考虑工件释放时间和柔性维护的单机调度问题为的加工时间；为的污染量；为的释放时间；为工件的开始加工时间；为的完工时间；为机器加工之后的机器役龄；为机器加工之前的机器役龄。决策变量：如果工件在第个位置加工，则，否则；
9、：如果在加工工件之前执行维护，则，否则。根据问题描述及符号表示，建立如下整数规划模型：。，；（），；（），；（），；（），；（），；（），；（），；（），；（）（），；（），；（），；（），；（），。（）其中：目标函数为最小化最大完工时间。约束（）和约束（）分别保证每个工件只能放在一个位置加工，每个位置只能安排一个工件；约束（）表示的加工时间；约束（）表示的释放时间；约束（）表示的污染量；约束（）表示的完工时间；约束（）表示的开始加工时间不得早于其释放时间；约束（）确保工件的开始加工时间不早于其紧前工件的完工时间与可能执行的清洁活动之和；约束（）表示该系统的初始条件，即机器初始役龄为，无需执行
10、清洁活动；约束（）和约束（）分别表示在加工之前的机器役龄和在加工之后的机器役龄；约束（）保证机器连续工作的役龄不大于；约束（）和约束（）为变量类型及非负约束。启发式算法 最优调度的性质性质，为 难的。证明在不考虑工件加工时间的情况下，包括清洁活动在内的所有工件（将清洁活动视为特殊工件）均在零时刻到达且都具有相同的污染量时，问题等同于具有装箱容量和物品尺寸的装箱问题。装箱问题描述如下：给定个尺寸为的物品和多个尺寸为的箱子，将这些物品装入箱子，使容纳个物品的箱子数量最小。对于，问题，在不考虑工件加工时间的情况下，所有工件均在零时刻到达且污染量均相同时，值仅取决于调度中的批次数，而与加工批次的顺序无
11、关。等价地，考虑一个箱子容量为的装箱问题，取最大机器役龄，对于每个工件，对应定义一个尺寸为的物品。装箱问题中放入同一个箱中的物品视为调度问题中同一批次加工的工件集合。由于最佳装箱方案使所用箱子数最少，且 取决于批次的数量，装箱问题的最佳装箱方案即为调度问 题 的 最 佳 调 度 方 案。因 此，问题在工件到达时间相同、机器役龄相等情况下的特例等价于装箱问题。等 已经证明装箱问题为 难的，而，问题考虑了工件的释放时间和加工时间，复杂度不低于装箱问题，因此，问题也是 难的。证毕。记 是部分调度，（）为 中最后一个工件的完成时间，（）为 中第个工件的开始加工时间。性质，问题，同一批次内的工件应按最早
12、到达时间（，）优先规则进行排序。证明假设最优调度，中 由 工 件计算机集成制造系统第 卷，形成的批次不满足 规则，其中，且（），可 得 加 工后 机 器 处 于 空 闲 状 态，采 用 规则重新调整该批次中的工件顺序，从而获得另一最佳调度，这 与 假 设 矛 盾，原 命 题得证。性质 调 度，如果（），（），则 将移 至，可 得 新 调 度，使 得 （）（）。证明首先，由于（），（），为 可 行 调 度。对 于 调 度，（）（），（）；对 于 调 度，（）（），（）。在 调 度的子调度 中可能存在空闲时间，而在调度中，这些空闲时间可能被占用，因此有（）（），进而得到（）（）。考虑到机器的役龄和
13、 的允许开始加工时间，可得 （）（）。证毕。性质调 度，若在中存在一个工件，满足，（），（），则将与互换位置可得新调度，使得 （）（）。证明首 先，由 于，（），（），为可行调度。对于调度，（）（），（）；对于调度，（）（），（）。将与互换位置，如果调度中的子调度 中无空闲时间，则有（）（）；如果调度中的子调度 中存在空闲时间，则有（）（）。因此，无论 中有无空闲时间，都有（）（），从而有（）（），即（）（）。考虑到机器的役龄和 的允许开始加工时间，可得 （）（）。证毕。性质如果所有未加工工件在当前时刻前均已到达，则该问题可转化为装箱问题，采用最大污染量最优适应（，）算法对未加工工件安排加工。
14、证明如果所有未加工工件在当前时刻前均已到达，则可将问题转化为所有工件（这里指所有未加工工件）均在零时刻到达的情况。因为目标函数为 ，只需减少后续执行清洁活动的次数即可实现目标函数的最小化，所以可将考虑清洁活动的问题简化为 难的装箱问题。因此，可以采用已知解决装箱问 题 的最 优 递减匹 配（，）算法 求解该问题。此处，将 算法转化为 ，即对工件的污染量进行降序排列，随后采用最优适应（，）安排工件加工。证毕。启发式算法由上述最优调度的性质可给出启发式算法 最早到达最长加工时间最大污染量优先的最优适应（，）算法，算法的整体运行流程如图所示。步骤对工件进行 排序，排序后形成序列，。步骤在时刻加工，令
15、 为当前机器的役龄，第期李小林 等：考虑工件释放时间和柔性维护的单机调度问题，。步骤如果 ，则转步骤；否则，转步骤。步骤令；，如果非空，则根据性质，选择中加工时间最长的工件在 处加工，令 ，转步骤；否则，转步骤。步骤令，如果非空，则在 处执行，令 ，转步骤；否则，转步骤。步骤是中的第个工件，令。如果（），则在 处执行，令 ，转步骤；否则，转。如果 （），则在 （），（）处 加 工，令 （），（），（）（），转步骤；否则，转。如果是中最后一个工件，则在 处执行，令 ，转步骤；否则，转。步骤如果，则令，转步骤；否则，算法终止。步骤在 处 执 行，令 ，转步骤。步骤令；，如果非空，则根据性质，选择工
16、件在 处加工，令 ，转步骤；否则，转步骤。下面采用一个实际生产案例说明算法应用效果及流程。晶圆制造中，研磨、抛光等多处制程后均需清洗，即将晶圆浸入清洁剂来去除表面的各种污染物，清洁剂中会积聚金属杂质，当金属杂质的浓度累积超过 时，需要更换清洁剂以免对晶圆表面造成二次污染，维护活动的处理时间固定为 。表所示为每个晶圆的加工时间、污染度和释放时间。表实例参数 （）根据 规则，可得该问题的调度甘特图如图所示，启发式算法的调度结果为，等于 输出的最优解。具体步骤如下：（）选择加工，此时未加工工件列表为，机器役龄 。工件的完工时间为，即为下一个决策时刻。（）工件和可以在此时加工，因为的加工时间较长，所以选择加工。此时工件列表为，机器役龄 。的完工时间为，即为下一个决策时刻。（）只有可以加工。此时工件列表为，机器役龄 。的完工时间为，即为下一个决策时刻。（）由于机器役龄已经为，当前没有已到达工件可以在此时加工，立即执行清洁活动，清洁活动结束时间为，即为下一个决策时刻。（）只有可以加工。此时工件列表为，机器役龄 。的完工时间为，即为下一个决策时刻。（）没有立刻可以加工的工件，选择工件在 时加工。此时
