两阶段车间作业排序问题的研究

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

本文关键词： 两阶段自由车间流水车间近似算法最坏情况界　出处：《浙江理工大学》2016年硕士论文　论文类型：学位论文

【摘要】：本文主要研究了两阶段车间作业排序问题:第一类是两阶段自由作业排序问题,第二类是两阶段混合车间作业排序问题。研究的重点是,证明这些问题的计算复杂性,设计问题的近似算法,并对算法的最坏情况界进行证明。全文共分为四章。具体如下:第一章简要的介绍排序的基本理论。第二章主要研究一类新型两阶段自由作业排序问题。第一阶段是自由车间,第二阶段是流水车间,目标是极小化最大完工时间。其中要求工件一旦进入流水车间的两台机上加工,必须完成流水车间加工才可进行下一阶段任务。本章分两种情形,目标均是极小化最大完工时间。情形一:考虑一般的情况,第一阶段机器为m台,第二阶段机器为两台,本章提出一个近似算法,并证明其最坏情况界为2;情形二:第一阶段机器为一台,第二阶段机器为两台,本文对问题进行复杂性证明,证明该问题是NP难问题,并给出一个5/3-近似算法及其最坏情况界证明。第三章主要研究一类两阶段混合车间作业排序问题。第一阶段是自由车间共两台机,第二阶段是流水车间共两台机。其中工件可选择任一阶段的车间进行加工,目标是极小化最大完工时间。本文对问题的复杂性进行证明,证明该问题是一般NP难问题,同时提出一个近似算法,并证明其最坏情况界为27/14。第四章总结全文并提出相关问题进一步的研究方向。
[Abstract]:In this paper, we mainly study the two-stage job-shop scheduling problem: the first is the two-stage free job scheduling problem, the second is the two-stage hybrid workshop scheduling problem. Prove the computational complexity of these problems, design the approximate algorithm of the problem. And prove the worst-case bound of the algorithm. The full text is divided into four chapters. The details are as follows:. The first chapter briefly introduces the basic theory of sorting. The second chapter mainly studies a new type of two-stage free job scheduling problem. The first stage is the free workshop. The second stage is the income workshop, with the goal of minimizing the maximum completion time, which requires the workpiece to be processed on two machines once it enters the income workshop. Income workshop must be completed before the next phase of the task. This chapter is divided into two cases, the goal is to minimize the maximum completion time. Case 1: considering the general situation, the first stage of the machine is m. There are two machines in the second stage. In this chapter, an approximate algorithm is proposed and its worst-case bound is proved to be 2. Case two: one machine in the first stage and two machines in the second stage. In this paper, we prove the complexity of the problem and prove that the problem is NP-hard. A 5 / 3-approximation algorithm and its worst-case bound proof are given. In Chapter 3, we mainly study a class of two-stage hybrid shop scheduling problem. The first stage is a two-machine free workshop. In the second stage, there are two machines in income workshop, in which the workpiece can be processed in any stage, and the goal is to minimize the maximum completion time. The complexity of the problem is proved in this paper. It is proved that this problem is a general NP-hard problem, and an approximate algorithm is proposed, and the worst-case bound is proved to be 27 / 14. 4th. The full text is summarized and the further research directions of related problems are proposed.
【学位授予单位】：浙江理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O223

【相似文献】