带学习效应的一些排序问题研究

发布时间：2018-05-01 07:36

本文选题：排序 + 学习效应　；参考：《华东理工大学》2017年硕士论文

【摘要】：排序问题作为一类在管理科学、计算科学和控制科学等领域有着广泛应用的问题,近年来受到了广泛的关注。本文基于依赖于工件加工位置的学习效应,研究了单机和平行机环境下的三个排序问题:最小化时间表长的两台平行机问题,最小化加权完工时间和的单机排序问题以及最小化最大延迟的单机排序问题。这三个问题均为NP-hard问题。对于平行机上带学习效应的时间表长问题,本文首先建立了求解该问题最优解的整数规划模型,其次,基于模拟退火算法给出了该问题的近似算法SA,并证明了该算法依概率1全局收敛到最优解,并通过数值模拟对所提出的算法进行了性能分析。数值模拟结果表明,本文提出的近似算法SA可以达到最优值的99%,准确度高,算法较有效。对于单机环境下带学习效应的最小化加权完工时间和问题,本文讨论了它的三种特殊情形:P_j=P,w_j=w以及w_j =kP_j,说明了在这三种特殊情况下,问题均为多项式时间可解的,分别给出了问题的算法并证明了算法的最优性。我们还研究了单机环境下带学习效应的最小化最大延迟问题,讨论了问题的三种特殊情形:P_j=P,d_j= d以及d_j= kP_j,说明了在这三种特殊情况下,问题均为多项式时间可解的,分别给出了问题的算法并证明了算法的最优性。
[Abstract]:As a class of problems in the fields of management science, computational science and control science, sort problems have been widely used in recent years. Based on the learning effect dependent on the working position of the workpiece, this paper studies three sorting questions in single and parallel machine environments: two parallel machine problems that minimize the length of the timetable, The problem of minimizing the weighted completion time and single machine sorting and minimizing the single machine ordering with maximum delay. These three problems are all NP-hard problems. For the long time problem with learning effect on parallel machines, this paper first establishes an integer programming model for solving the optimal solution of the problem. Secondly, the simulated annealing algorithm is given. The approximate algorithm SA of the problem is proved that the algorithm converges to the optimal solution according to the probability 1, and performs the performance analysis of the proposed algorithm by numerical simulation. The numerical simulation results show that the approximate algorithm SA proposed in this paper can reach 99% of the optimal value, the accuracy is high, and the calculation method is more effective. To minimize the weighted completion time and problem, this paper discusses three special cases of it: P_j=P, w_j=w and w_j =kP_j. It shows that in these three special cases the problem is polynomial time solvable, the algorithm of the problem is given and the optimality of the algorithm is proved. We also study the minimization of the learning effect in a single machine environment. The problem of maximum delay is discussed. Three special cases of the problem are discussed: P_j=P, d_j= D and d_j= kP_j. It shows that in these three special cases the problem is polynomial time solvable, the algorithm is given and the optimality of the algorithm is proved.

【学位授予单位】：华东理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O223

【相似文献】