SIA OpenIR  > 数字工厂研究室
Alternative TitleStudy of Hybrid Flow Shop Scheduling Optimization based on Lagrangian Relaxation
Thesis Advisor朱军 ; 刘昶
Keyword混合流水车间 拉格朗日松弛 调度
Call NumberF252/D58/2015
Degree Discipline模式识别与智能系统
Degree Name硕士
Degree Grantor中国科学院沈阳自动化研究所
Place of Conferral沈阳
Abstract混合流水车间调度问题一般存在多道加工阶段,并且至少有一个阶段存在多个并行工位,调度不仅要解决多个工件在各阶段的排序问题,而且还要解决各阶段上并行机的分配问题,是一类典型的NP-难问题。本文以半导体封装测试生产过程为背景,根据提炼出的半导体封装测试过程中的JIT模式下的提前/拖期问题,等待时间受限问题以及降低生产过程中能源消耗这三类问题进行研究,设计相应的拉格朗日松弛求解算法。主要研究内容如下: 针对半导体生产过程中JIT生产模式研究了混合流水车间提前/拖期调度问题,并分别设计了基于容量约束进行松弛和基于顺序约束进行松弛的两种拉格朗日松弛算法来进行求解。对大规模调度模型和小规模调度模型进行仿真验证的结果表明:在处理小规模问题时这两种松弛方法均能在较短的时间内获得近乎相同的调度结果,然而在处理大规模问题时松弛容量约束法比松弛顺序约束法的调度效果要好一些。 针对半导体封装测试的键合-等离子清洗-塑封过程中出现的等待时间受限这一实际问题来进行问题建模和算法的研究。首先建立了等待时间受限的混合流水车间调度模型,然后设计了基于工件分解策略的拉格朗日松弛算法来进行求解。该算法通过将机器容量约束松弛到目标函数中,将得到的松弛问题进而分解为一系列易于求解的工件级子问题来进行求解。采用动态规划算法求解子问题,次梯度算法进行乘子的更新,并设计了一个贪婪算法来进行解的可行化。通过对测试结果表明所设计的拉格朗日松弛算法能够在较短的时间内产生较好的近优解,且等待时间较小时拉格朗日松弛算法的收敛速度相对要快一些。 研究了面向节能的混合流水车间调度问题,针对该问题设计了一种拉格朗日松弛算法进行求解。该算法通过将工件的加工顺序约束进行松弛,使原问题分解为一系列子问题,然后利用动态规划算法对子问题进行求解,采用次梯度算法进行乘子更新,并设计了一个两阶段启发式算法来进行解的可行化。最后通过对不同规模问题的仿真测试表明算法能够有效的降低生产过程中的能耗。
Other AbstractHybrid 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.
Contribution Rank1
Document Type学位论文
Recommended Citation
GB/T 7714
丁小丽. 基于拉格朗日松弛的混合流水车间优化调度研究[D]. 沈阳. 中国科学院沈阳自动化研究所,2015.
Files in This Item:
File Name/Size DocType Version Access License
基于拉格朗日松弛的混合流水车间优化调度研(1539KB) 开放获取CC BYApplication Full Text
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[丁小丽]'s Articles
Baidu academic
Similar articles in Baidu academic
[丁小丽]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[丁小丽]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.