论文部分内容阅读
混合流水车间调度问题一般存在多道加工阶段，并且至少有一个阶段存在多个并行工位，调度不仅要解决多个工件在各阶段的排序问题，而且还要解决各阶段上并行机的分配问题，是一类典型的NP-难问题。本文以半导体封装测试生产过程为背景，根据提炼出的半导体封装测试过程中的JIT模式下的提前/拖期问题，等待时间受限问题以及降低生产过程中能源消耗这三类问题进行研究，设计相应的拉格朗日松弛求解算法。主要研究内容如下: 针对半导体生产过程中JIT生产模式研究了混合流水车间提前/拖期调度问题，并分别设计了基于容量约束进行松弛和基于顺序约束进行松弛的两种拉格朗日松弛算法来进行求解。对大规模调度模型和小规模调度模型进行仿真验证的结果表明:在处理小规模问题时这两种松弛方法均能在较短的时间内获得近乎相同的调度结果，然而在处理大规模问题时松弛容量约束法比松弛顺序约束法的调度效果要好一些。 针对半导体封装测试的键合-等离子清洗-塑封过程中出现的等待时间受限这一实际问题来进行问题建模和算法的研究。首先建立了等待时间受限的混合流水车间调度模型，然后设计了基于工件分解策略的拉格朗日松弛算法来进行求解。该算法通过将机器容量约束松弛到目标函数中，将得到的松弛问题进而分解为一系列易于求解的工件级子问题来进行求解。采用动态规划算法求解子问题，次梯度算法进行乘子的更新，并设计了一个贪婪算法来进行解的可行化。通过对测试结果表明所设计的拉格朗日松弛算法能够在较短的时间内产生较好的近优解，且等待时间较小时拉格朗日松弛算法的收敛速度相对要快一些。 研究了面向节能的混合流水车间调度问题，针对该问题设计了一种拉格朗日松弛算法进行求解。该算法通过将工件的加工顺序约束进行松弛，使原问题分解为一系列子问题，然后利用动态规划算法对子问题进行求解，采用次梯度算法进行乘子更新，并设计了一个两阶段启发式算法来进行解的可行化。最后通过对不同规模问题的仿真测试表明算法能够有效的降低生产过程中的能耗。