订单排序 约束链排序 半在线排序 NP-hard 竞争比.doc

【关键词】订单排序 约束链排序 半在线排序 NP-hard 竞争比【英文关键词】Order scheduling Chain-precedence constraints scheduling Semi-online scheduling NP-hardness Competitive ratio订单排序论文：一类订单排序及两类平行机排序问题【中文摘要】排序论作为最优化理论的重要组成部分,在计算机系统、运输调度、生产管理等诸多领域有着广泛的应用,并且取得了大量有意义的成果。订单排序问题是一类现实意义很强的排序问题,因而具有一定的研究价值。本文讨论了这类问题的计算复杂性。近年来,伴随着生产生活的需要而产生的工件具有优先加工约束的排序问题和半在线(semi-online)模型越来越受到大家的重视。本文就三台同型机上约束链的排序问题和两台带准备时间的同类机半在线问题进行了研究。论文结构安排如下：第一章为绪论部分,首先介绍了排序问题的产生、意义及研究现状,然后给出了必要的预备知识,最后介绍了本文主要研究的问题及其结果。第二章主要讨论极小化带多工类工件订单的完工范围问题：考虑同一类工件放在一起连续加工,任一工件的完工时间为其所在类中全部工件完工时的时间的情况,以订单的完工时间范围最小为优化目标,证明了此问题为NP-hard.并给出了相应的分枝定界算法。第三章主要讨论三台同型机上四个约束链的排序问题,在说明此问题为NPhard的基础上,通过一个伪多项式时间算法和一个完全多项式时间近似方案来描述此问题的复杂性。第四章主要讨论两台带准备时间的同类机半在线排序问题,文中分析了任意算法竞争比的下界,给出了一个近似算法,并证明其竞争比为一分段函数。【英文摘要】Scheduling is an important part of combinatorial optimization which is widelyused in computer system, transports, production management and other sectors.Order scheduling is a profound practical scheduling model. In this paper wemainly deal with its computational complexity. In recent years, with the need ofproduction, people pay more attention to chain precedence constraints schedulingand semi-online scheduling. We also consider these two scheduling problems onparallel machines in the paper.The thesis is organized as follows.In the first chapter, we give an introduction of the basic knowledge aboutscheduling, semi-online scheduling and the main research results obtained in thisthesis.In the second chapter, we study scheduling problem of minimizing the rangeof order completion times with multiple job classes. We prove that the schedulingproblem is N P hard and present a branch and bound algorithm.In the third chapter, we study the problem of scheduling four chains on threeidentical parallel machines. We explain the NP-hardness of this problem, whichcomputational complexity is characterized by giving a pseudo-polynomial timealgorithm and a F P T AS.In the fourth chapter, we study the semi-online scheduling problem on twouniform machines with set-up time. We present an algorithm and the correspond-ing competitive ration for the considered problem.【目录】一类订单排序及两类平行机排序问题摘要4-5ABSTRACT5第一章 绪论7-131.1 排序的定义与符号7-81.2 计算复杂性及问题求解8-111.3 在线与半在线排序11-121.4 本文的主要工作12-13第二章 极小化带多工类工件订单的完工范围问题13-202.1 问题背景及研究现状13-142.2 数学模型142.3 问题为NP-hard的证明14-172.4 分枝定界算法17-192.5 本章小结19-20第三章 三台同型机上四个约束链的排序问题20-273.1 问题背景及研究现状20-213.2 问题描述213.3 问题的动态规划算法21-253.4 完全多项式时间近似方案(FPTAS)25-263.5 本章小结26-27第四章 两台带准备