基于拉格朗日松弛的混合流水车间优化调度研究

CORC > 沈阳自动化研究所 > 中国科学院沈阳自动化研究所 > 数字工厂研究室

题名	基于拉格朗日松弛的混合流水车间优化调度研究
作者	丁小丽
学位类别	硕士
答辩日期	2015-05-26
授予单位	中国科学院沈阳自动化研究所
授予地点	中国科学院沈阳自动化研究所
导师	朱军 ; 刘昶
关键词	混合流水车间拉格朗日松弛调度
其他题名	Study of Hybrid Flow Shop Scheduling Optimization based on Lagrangian Relaxation
学位专业	模式识别与智能系统
中文摘要	混合流水车间调度问题一般存在多道加工阶段，并且至少有一个阶段存在多个并行工位，调度不仅要解决多个工件在各阶段的排序问题，而且还要解决各阶段上并行机的分配问题，是一类典型的NP-难问题。本文以半导体封装测试生产过程为背景，根据提炼出的半导体封装测试过程中的JIT模式下的提前/拖期问题，等待时间受限问题以及降低生产过程中能源消耗这三类问题进行研究，设计相应的拉格朗日松弛求解算法。主要研究内容如下：针对半导体生产过程中JIT生产模式研究了混合流水车间提前/拖期调度问题，并分别设计了基于容量约束进行松弛和基于顺序约束进行松弛的两种拉格朗日松弛算法来进行求解。对大规模调度模型和小规模调度模型进行仿真验证的结果表明：在处理小规模问题时这两种松弛方法均能在较短的时间内获得近乎相同的调度结果，然而在处理大规模问题时松弛容量约束法比松弛顺序约束法的调度效果要好一些。针对半导体封装测试的键合-等离子清洗-塑封过程中出现的等待时间受限这一实际问题来进行问题建模和算法的研究。首先建立了等待时间受限的混合流水车间调度模型，然后设计了基于工件分解策略的拉格朗日松弛算法来进行求解。该算法通过将机器容量约束松弛到目标函数中，将得到的松弛问题进而分解为一系列易于求解的工件级子问题来进行求解。采用动态规划算法求解子问题，次梯度算法进行乘子的更新，并设计了一个贪婪算法来进行解的可行化。通过对测试结果表明所设计的拉格朗日松弛算法能够在较短的时间内产生较好的近优解，且等待时间较小时拉格朗日松弛算法的收敛速度相对要快一些。研究了面向节能的混合流水车间调度问题，针对该问题设计了一种拉格朗日松弛算法进行求解。该算法通过将工件的加工顺序约束进行松弛，使原问题分解为一系列子问题，然后利用动态规划算法对子问题进行求解，采用次梯度算法进行乘子更新，并设计了一个两阶段启发式算法来进行解的可行化。最后通过对不同规模问题的仿真测试表明算法能够有效的降低生产过程中的能耗。
索取号	F252/D58/2015
英文摘要	Hybrid Flow Shop Scheduling Problem (HFSP) usually have multiple processing stages, and there are at least one stage to have multiple parallel machines. Solve of the problem not only need to get the scheduling of multiple jobs at each stage, but also to solve the assignment problem in each stage of the parallel machine, which is a typical NP- hard problem. This paper is on the background of production process of semiconductor assembly and test, study the earliness / tardiness problem refining in JIT mode, the problem of limited waiting time and the reduce energy consumption in the production process of the semiconductor assembly and test. And design the corresponding lagrange relaxation algorithm for solving the three problems. The main research contents are as follows: Study problem of hybrid flow shop scheduling problem with JIT production model in the process of semiconductor manufacturing, and design the corresponding Lagrange relaxation algorithm. The simulation of large-scale and small-scale scheduling model results show that: In the processing of small scale problems, these two kinds of relaxation method can obtain almost the same scheduling results in a relatively short period of time. However, in dealing with large scale problems, capacity constraint method is better than sequence constraint method of relaxation the scheduling, which can obtain a better objective function value. In the bonding-plasma cleaning-plastic process of semiconductor packaging and testing, it requires the waiting time of the wafer between adjacent stages do not exceed a certain time limit, thus forming the hybrid flow shop scheduling problem with limited waiting time. Firstly, we established the model of hybrid flow shop scheduling problem with limited waiting time, and then designed the lagrangian relaxation algorithm of workpiece decomposition strategy to solve the problem. By introducing machine capacity constraints into the objective function, the original problem was decomposed into a series of job level sub-problems which is easy to solve. The algorithm uses the dynamic programming algorithm to solve the sub problem, a gradient algorithm to update the multipliers, and designs a greedy algorithm to make the result into a feasible solutions. Simulation results demonstrated that the proposed method could generate near optimal schedules in an acceptable computational time. And the convergence speed is faster when the waiting time is smaller. Study the hybrid flow shop scheduling problem based on saving energy, a Lagrange relaxation algorithm is designed to solve the problem. By introducing precedence constraints into the objective function, the original problem was decomposed into a series of sub-problems. Then the author designed a dynamic programming algorithm to solve these sub-problems. The method of updating multiples was sub-gradient algorithm. And designed a two stage heuristic algorithm to contract the feasible solutions. Finally, through the scale on different issues test show that the algorithm can reduce the energy consumption of the production process effectively.
语种	中文
产权排序	1
页码	59页
内容类型	学位论文
源URL	[http://ir.sia.ac.cn/handle/173321/16740]
专题	沈阳自动化研究所_数字工厂研究室
推荐引用方式 GB/T 7714	丁小丽. 基于拉格朗日松弛的混合流水车间优化调度研究[D]. 中国科学院沈阳自动化研究所. 中国科学院沈阳自动化研究所. 2015.