依赖于资源分配的排序问题研究

发布时间：2018-07-03 19:02

本文选题：排序 + 学习效应　；参考：《上海大学》2015年博士论文

【摘要】：排序论作为运筹学的一个分支,有着深刻的实际背景和广阔的应用前景.近年来,在排序问题的研究过程中,加工方式、目标函数以及用来解决问题的方法上不断地向多样性发展,从而产生了许多新型的现代排序问题.这些现代排序问题比经典排序问题更为复杂,在实际应用中也更有意义.本文研究了现代排序中具有复杂加工时间的资源分配排序问题,其主要内容可以概括如下：第一章首先介绍了排序问题的定义、分类、求解以及现代排序问题的特征,其次介绍了几类排序问题的研究背景,最后概述了本文的主要工作.第二章研究了工件具有截断学习效应,恶化效应和资源分配的单机排序问题.假设工件的实际加工时间依赖于工件的位置、开工时间、可分配的资源数量以及控制参数.我们找寻最优的工件排序与最优的资源分配,来解决三类目标费用极小化问题：(1)线性(凸)资源模型下,总费用最小化问题；(2)凸资源模型中,有限控制费用下,完工费用最小化问题；(3)凸资源模型中,有限完工费用下,控制费用最小化问题.并证明了上述问题都有多项式时间算法.第三章研究了在成组技术条件下具有学习效应,恶化效应和资源分配的单机排序问题.假设工件的实际加工时间依赖于工件的位置、所在组的位置、开工时间以及可分配的资源数量,组间的调整时间依赖于组的位置和可分配给组的资源.对于目标函数为最小化总加权时间表长和总资源成本的问题,分别在线性和凸资源分配函数下,证明了每组工件数相等时,该排序问题是多项式时间可解的.第四章研究了加工时间同时依赖于资源分配和恶化效应的变速机排序问题.假设工件的实际加工时间是开工时间和资源消耗量的函数.我们讨论了在线性和凸资源分配函数下,寻找最优工件排序与最优资源分配,分别使得两个总费用函数极小的排序问题.并证明了变速机数量为常值时,这些问题存在多项式时间算法.第五章针对本文讨论的某些资源分配排序模型,对后期研究工作进行了展望.
[Abstract]:As a branch of operational research, sequencing theory has a profound practical background and broad application prospects. In recent years, the processing methods, objective functions and methods used to solve the problems have been developing to diversity in the research process of scheduling problems, which has resulted in many new modern scheduling problems. These modern scheduling problems are more complex than classical scheduling problems and are more meaningful in practical applications. In this paper, the problem of resource allocation with complex processing time in modern sorting is studied. The main contents can be summarized as follows: in the first chapter, the definition, classification, solution and characteristics of the scheduling problem are introduced. Secondly, the research background of several kinds of scheduling problems is introduced, and the main work of this paper is summarized. In chapter 2, we study the single machine scheduling problem of jobs with truncation learning effect, deterioration effect and resource allocation. It is assumed that the actual processing time of the workpiece depends on the position of the workpiece, the starting time, the number of allocated resources and the control parameters. We search for optimal job ranking and optimal resource allocation to solve three kinds of target cost minimization problems: (1) the total cost minimization problem in the linear (convex) resource model; (2) in the convex resource model, under the finite control cost, (3) in the convex resource model, the control cost is minimized under the finite completion cost. It is proved that all the above problems have polynomial time algorithms. In the third chapter, we study the single machine scheduling problem with learning effect, deterioration effect and resource allocation under the condition of group technology. It is assumed that the actual processing time of the workpiece depends on the position of the workpiece, the position of the group, the starting time and the number of allocated resources, and the adjustment time between the groups depends on the position of the group and the resources that can be allocated to the group. For the problem that the objective function is to minimize the total weighted schedule length and the total resource cost, it is proved that the scheduling problem is polynomial time solvable under the linear and convex resource allocation functions, respectively. In chapter 4, we study the transmission scheduling problem in which processing time depends on both resource allocation and deterioration effect. It is assumed that the actual processing time of the workpiece is a function of the starting time and the consumption of resources. In this paper, we discuss the problem of finding the optimal job ordering and optimal resource allocation under linear and convex resource allocation functions so that the two total cost functions are minimized, respectively. It is proved that there are polynomial time algorithms for these problems when the number of transmissions is constant. In the fifth chapter, some resource allocation scheduling models discussed in this paper are discussed, and the later research work is prospected.
【学位授予单位】：上海大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O223

【相似文献】