两类加工时间可控的排序问题研究

发布时间：2018-05-26 04:10

本文选题：单机排序 + 退化效应　；参考：《沈阳师范大学》2017年硕士论文

【摘要】：排序问题作为典型的组合最优化问题的一种。设有一定数量的机器和工件或任务。给出所有任务工件的加工时间和加工任务的顺序。题目是确定任务在每个处理机上的处理顺序,使选定的目标函数最优。在很多经典调度问题中,任务处理所需的时间是给定的常量或是一些随机变量。然而在实际生产中,任务的加工所需要的时间可能是一个和资源分配、任务在序列中的次序相关的函数,因此便产出现了一些新型的排序题目。第一章,介绍了本文的选题依据,曾经提过类似该问题的文章以及本文所做的工作。第二章,考虑包含多个工期窗口和退化维护的单机排问题。设任务的加工时间是一个凸函数。该凸函数与分配给这个任务的资源有关,也与所在的次序和退化效应有关。我们的目标是确定最佳维护的位置和多个最佳施工工期时间窗口的大小,分配给每个时间窗口的作业,分配给每个工件的资源和最佳的作业调度。尽量减少提前,误工的总成本,工期窗口的开始时间、大小,资源等构成的总用度。用到求解指派问题得出了复杂度为(7)(8)4O n和(7)(8)m(10)3nO的优化算法,其中是n工件数量。第三章,研究带有公共工期且工件的加工时间是与位置的负荷以及资源有关的排序问题。工件的加工时间是一个和资源分配、工件在排序中的位置以及负荷有关的凸函数,所有任务具有一个公共工期。我们的目标是确定最佳工期的位置、分配给每个任务的资源、任务排序序列,尽量减少提前、误工的总成本。用到指派问题得出了复杂度为(7)(8)3O n的优化算法。最后,总结本文,并给出通过本文可进一步考虑的题目。
[Abstract]:Scheduling problem is one of the typical combinatorial optimization problems. Having a certain number of machines and workpieces or tasks. The processing time and order of all tasks are given. The problem is to determine the processing order of tasks on each processor to optimize the selected objective function. In many classical scheduling problems, the task processing time is a given constant or some random variables. However, in actual production, the time required for processing tasks may be a function related to the order of resource allocation and tasks in the sequence, so some new sorting problems have emerged. The first chapter introduces the basis of this paper, has mentioned similar issues and the work of this paper. In the second chapter, the single machine scheduling problem including multiple duration windows and degenerate maintenance is considered. Let the processing time of the task be a convex function. The convex function is related to the resources assigned to the task, as well as to the order in which it is located and the degenerate effect. Our goal is to determine the optimal location of maintenance and the size of multiple optimal construction time windows, assign jobs to each time window, assign resources to each job and optimal job scheduling. Try to reduce the total cost of advance, delay, duration window start time, size, total cost of resources, etc. By solving the assignment problem, the optimization algorithms with the complexity of 7 / 8 / 4O / n and 10 / 3nO are obtained, in which the number of jobs is n. In chapter 3, we study the scheduling problem in which the processing time of the workpiece with common duration is related to the load of position and the resource. The processing time of a job is a convex function related to the allocation of resources, the position of the job in the sorting and the load. All tasks have a common duration. Our goal is to determine the optimal time frame, assign resources to each task, sequence tasks, and minimize the total cost of early, delayed work. By using the assignment problem, an optimization algorithm with a complexity of 7 / 8 / 3O / n is obtained. Finally, this paper is summarized, and the topic that can be considered further through this paper is given.
【学位授予单位】：沈阳师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O223

【参考文献】