曲阜师范大学博士学位论文原创性声明
曲阜师范大学博士学位论文使用授权书
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 Total 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
§2.3.3 The Special Case of ωj=1 for j=1,...,n
§2.4 Conclusion
Chapter Ⅲ Parallel-batch Scheduling on Unrelated Machines
§3.1 Introduction
§3.2 Problem Statement and Notation
§3.3 The Unbounded Parallel-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 Rcjcction
§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
§4.4.1 Problem 1丨B,pj=αjt丨ΣCj
§4.4.2 Problem 1丨B,pj=αjt丨ΣωjCj
§4.5 Conclusion
Chapter Ⅴ Single-machine Parallel-batch Scheduling with Proportional-linear Deterioration and Rejection
§5.1 Introduction
§5.2 Problem Statement
§5.3 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 SingIe-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