基于拉格朗日松弛法的调度算法研究

发布时间：2018-02-14 12:06

本文关键词： 调度拉格朗日松弛法逐步次梯度法可行解　出处：《上海交通大学》2014年硕士论文　论文类型：学位论文

【摘要】：调度作为生产制造系统中一个重要的环节，其质量的好坏直接影响到生产的成本以及企业的服务声誉。但是在实际生产过程中，处理机的数量和种类、作业的性质、加工要求和限制、资源的种类和数量及其对加工的影响，以及性能指标等是错综复杂的，这使得产生一个好的调度通常是很难的。而且研究表明，大部分调度问题都具有NP-hard性，因此在实际应用中，一个有效的调度算法的目的是在合理的计算时间内得到一个较好的近似解。大量文献表明基于拉格朗日松弛的调度算法是一种求解NP-hard的调度问题的有效算法，，其不仅能提供一个较好的近似最优解，还能为近似解提供一个下界。但是，该算法的有效性依赖于所构造的对偶问题的求解效率以及可行化方法的优劣。本文的研究正是在现有研究工作的基础上，从这两个方面出发，首先将逐步次梯度法应用到对偶问题的求解，改善对偶问题的收敛速度，然后对可行化方法的设计进行了细致的分析研究，在几个关键环节上提出了新的策略，改善了可行解的质量。归纳起来，本论文主要做了以下四个方面的工作：从拉格朗日松弛法求解一般的优化问题出发，介绍了一般的异顺序的作业调度问题的数学规划模型，从松弛问题的构造及子问题的求解、对偶问题求解和解的可行化三个方面对基于LR的调度算法的求解框架进行了总结与归纳。针对标准的次梯度法收敛慢的问题，分析了次梯度法的求解特性，为了获取一个次梯度，其需要精确求解所有的子问题。受即时利用信息的思想启发，将逐步次梯度法应用到对偶问题的求解，每求解一个工件级的子问题就更新一次乘子，阐述了具体的求解步骤，并通过近似的定量分析推导出了一个确定初始步长的近似公式，通过大量的仿真验证了算法的有效性。为了提高可行解的质量，对可行化方法的设计展开了较为全面的研究，将其归纳为三个主要环节，对各个环节的不同做法进行了阐述，提出了大窗口策略与插入空闲时间策略，给出了可行化方法设计的指导思想。在不同的加工环境下对各个环节的不同做法进行大量的仿真比较。为了辅助调度算法的设计与改进，建立一个针对学术研究的可视化的调度算法仿真平台，尤其是针对基于LR的调度算法，该仿真平台能实时显示中间迭代过程，同时绘制松弛解和相应可行解的Gantt图，并能在可行解的Gantt图上手动调整操作的可行化开工时间，比较其对调度性能的影响。
[Abstract]:As an important link in manufacturing system, the quality of scheduling directly affects the cost of production and service reputation of enterprises, but in the actual production process, the number and type of processors, the nature of the job, Processing requirements and constraints, the types and quantities of resources and their impact on processing, and performance indicators are complex, which makes it difficult to produce a good scheduling, and studies show that most scheduling problems are NP-hard. Therefore, in practical application, the purpose of an effective scheduling algorithm is to obtain a better approximate solution within a reasonable computation time. A large number of literatures show that the Lagrangian relaxation scheduling algorithm is an effective algorithm for solving the NP-hard scheduling problem. It can not only provide a better approximate optimal solution, but also provide a lower bound for the approximate solution. The validity of this algorithm depends on the efficiency of the dual problem and the feasibility method. Firstly, the stepwise subgradient method is applied to the solution of duality problem to improve the convergence rate of duality problem, then the design of feasible method is analyzed and studied in detail, and a new strategy is put forward in several key links. The quality of feasible solution is improved. To sum up, this paper mainly does the following four aspects of work:. Starting from the Lagrangian relaxation method to solve the general optimization problem, the mathematical programming model of the general disordered job scheduling problem is introduced, which is based on the construction of the relaxation problem and the solution of the sub-problem. In this paper, the framework of LR-based scheduling algorithm is summarized in three aspects of the feasibility of solving dual problems. In view of the problem of slow convergence of the standard subgradient method, the characteristics of the subgradient method are analyzed. In order to obtain a subgradient, it is necessary to solve all the subproblems accurately, which is inspired by the idea of instant utilization of information. The stepwise subgradient method is applied to the solution of the dual problem. For each workpiece level subproblem, the multiplier is renewed, and the concrete solution steps are expounded, and an approximate formula for determining the initial step size is derived by the approximate quantitative analysis. The effectiveness of the algorithm is verified by a large number of simulations. In order to improve the quality of the feasible solution, the design of the feasible method is studied comprehensively, which is summed up into three main links, and the different methods of each link are expounded. The strategy of large window and the strategy of inserting idle time are put forward, and the guiding idea of the design of feasible method is given, and a large number of simulation comparisons are carried out in different processing environments. In order to aid the design and improvement of scheduling algorithm, a visual simulation platform for scheduling algorithm is established for academic research, especially for the LR-based scheduling algorithm. The simulation platform can display the intermediate iterative process in real time. At the same time, the Gantt diagram of the relaxation solution and the corresponding feasible solution is drawn, and the feasible start time of the operation can be manually adjusted on the Gantt diagram of the feasible solution to compare its influence on the scheduling performance.
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TB497

【共引文献】