分批排序及资源约束排序中若干问题

论文摘要

排序是组合优化的一个重要的分支.由于其坚实的应用背景和深刻的理论意义,它被广泛应用于工农业生产、运输业、管理科学和计算机科学等诸多领域.分批排序与机器有使用限制的排序都是新型的排序问题,因此吸引了国内外众多学者的关注.在经典排序问题中,通常假设工件的加工时间为常数.但在许多实际问题中,工件的加工时间可能与其开工时间或所排位置有着某种联系,由此产生一些工件的工时可变化的现代排序问题.本文就工件加工时间为常数或线性变化的分批排序及资源有约束排序中若干问题做了如下工作：1.第一章介绍了排序问题产生的主要背景以及相关基本知识.2.第二和第三章我们考虑了工件的加工时间是常数的分批排序问题.其中在第二章研究的是无限批容量下的同类机分批排序问题,目标是极小化加权总完工时间.我们给出了该问题的最优排序的性质,当机器的台数m为常数时,设计了一个时间复杂性为O（nm+2）的动态规划算法.第三章研究的是批容量无限和有限的无关机分批排序问题.对批容量无限排序模型,目标是极小化总完工时间,我们为工时一致性的情形设计了一个时间复杂性为O（nm+2）的动态规划算法；对批容量有限排序模型中的特殊情形pij=pi（1≤i≤m,1≤j≤n）,为若干不同目标,分别设计了最优算法及伪多项式时间算法.3.第四和第五章我们考虑了工件的加工时间是变量的分批排序问题.其中第四章研究的工件的实际加工时间为pj=αjt,其中αj被定义为工件的恶化率,t是开工时间.本章我们考虑了极小化最大完工时间和总完工时间问题.对极小化最大完工时间问题,对工件有同一到达时间情形,我们分别就单机和平行机问题设计了最优算法和FPTAS:对工件到达时间不一致情形,我们证明了其NP-难性,并就一特殊情形给出了多项式时间最优算法.对极小化总完工时间的单机问题,当工件的恶化率的个数是常数m（<n）时,我们设计了伪多项式时间算法.第五章研究的是线性成比例恶化模型即pj=αj（A+Dt）工件在单批处理机上的可拒绝分批排序,其中αj,A,D>0,目标是极小化被接收工件的最大完工时间加上被拒绝工件的总拒绝费用.我们首先证明该问题是NP-难的,然后给出了一伪多项式时间算法,最后设计了FPTAS.4.第六章考虑了混合工件的资源约束排序问题,其中部分工件的加工时间为常数,另一部分的工件的加工时间为pj=αjt目标是极小化最大完工时间.假设机器只有一个不可用区间,我们证明了单机问题是一般意义下的NP-难的,给出一4/3—近似算法,并证明了平行机问题是强NP-难的.

论文目录

• 中文摘要
• ABSTRACT
• Chapter Ⅰ Preliminaries
• §1.1 The Background of Scheduling
• §1.2 Model and Notation
• §1.3 Computational Complexity
• §1.4 NP-Completeness
• §1.5 Algorithm,Approximation Algorithms and Technique of Rounding
• Chapter Ⅱ Minimizing the Tot al Weighted Completion Time on Uniform Machines with Unbounded Parallel-batch
• §2.1 Introduction
• §2.2 Notation and Preliminaries
• §2.3 Dynamic Programming Algorithm
• §2.3.1 Optimal Schedules Properties
• §2.3.2 Algorithm and Example
• j=1'>§2.3.3 The Special Case of ω_j=1
• §2.4 Conclusion
• Chapter Ⅲ Parallel-batch Scheduling on Unrelated Machines
• §3.1 Introduction
• §3.2 Problem Statement and Notation
• §3.3 The Unbounded Parllel-batch Model
• §3.4 The Bounded Parallel-batch Model
• §3.4.1 The Case with General Parallel-batch Scheduling
• §3.4.2 The Case with Rejection
• §3.5 Conclusion
• Chapter Ⅳ Bounded Parallel-Batch Scheduling for Deteriorating Jobs
• §4.1 Introduction
• §4.2 Model Description and Preliminaries
• §4.3 Minimizing the Maxmum Completion Time
• §4.3.1 Identical Release Dates
• §4.3.2 Distinct Release Dates
• §4.4 Minimizing the（Weighted）Total Completion Time
• j=α_jt|∑C_j'>§4.4.1 Problem 1IB,p_j=α_jt|∑C_j
• j=α_jt|∑w_jC_j'>§4.4.2 Problem 1|B,p_j=α_jt|∑w_jC_j
• §4.5 Conclusion
• Chapter Ⅴ Single-machine Parallel-batch Scheduling with Proportional-linear Deterioration and Rejection
• §5.1 Introduction
• §5.2 Problem Statement
• §5.3 The NP-hardness
• §5.4 Pseudo-polynomial Time Dynamic Programming Algorithm
• §5.5 An Fully Polynomial Time Approximation Scheme
• §5.6 Conclusion
• Chapter Ⅵ Scheduling under Mixed Deterioration with Machine Availability Constrains
• §6.1 Introduction
• §6.2 Problem Description and Notation
• §6.3 The Single-machine Issue
• §6.3.1 The NP-hardness
• §6.3.2 The Approximation Algorithm
• §6.4 The Parallel-machine Issue
• §6.5 Conclusion
• References
• Papers Published in the Period of Ph.D Education
• Acknowledgement