臺灣博碩士論文加值系統

在此研究中，我們考慮當極小化最大延遲時間時，在具機器可用時間與機器合適度且工作具互斥性限制下，n個不可分割的工作和m台平行機台的排程問題。每台機器只有某些時間區段可以被安排處理工作，每個工作也只能被安排在某些特定的機器上，每個工作和機器上的每個可用的時間區段都有特定的服務水準，而只有當這個時間區段的服務水準高於或等於工作的服務水準時，此工作才能被安排在這個時間區段內，某些工作會屬於某個群組，且只有工作屬於不同群組能被放置於同一可用的時間區段中進行工作。
我們提出一個分枝界限演算法去尋找這個問題的最佳解。首先，我們提出一演算法基於最多剩餘工作之群組優先/最早截止時間優先(MJF/EDD)法則來得到上限。然後，我們網路流技術用來闡述可分割工作的排程問題並將其轉變成最大流量問題。我們提出一個由林正峰(2006)延伸而來的演算法，其結合網路流技術和二元搜尋法去找到該問題的最佳解，並將其結果作為我們的下限。最後，我們提出四個支配的法則來提升分枝界限法的效率。
實驗的分析顯示，所提出的淘汰法則是有效率的並且在分枝界限法中只有非常小的比例的節點被產生。在所有淘汰法則中，我們發現利用工作互斥限制式刪除的節點比例會隨著有群組的工作比例上升或群組的數目減少而增加。我們的演算法能用於15個工作、7台機器和3個群組問題下而得到一個最佳解。

In this paper we consider the problem of scheduling n non-preemptive jobs on m identical machines with machine availability, eligibility and incompatible job constraints when minimizing the maximum lateness. Each machine is not continuously available at all time and each job is only allowed to be processed on specific machines. Each job has to be processed at an availability interval with the same service level or higher. Some job belongs to a family and only jobs from different family may be processed in the same availability interval.
We propose a branch and bound algorithm to find out the optimal solution. Firstly, we propose an algorithm which bases on the Most Remaining Jobs Family First/Earliest Due Date First (MJF/EDD) rule to find an upper bound. Then, we use a network flow technique to model the scheduling problem with the job preemption into a series of maximum flow problems. We propose an algorithm which extends from the work of Lin (2006). Our algorithm combines a network flow technique and a binary search procedure to find an optimal solution for the scheduling problem with the job preemption and use the result as the lower bound. Finally, we use four dominance rules to increase the efficiency of the branch and bound algorithm.
Computational analysis shows that eliminating rules proposed is effective and very low percentage of nodes is generated by the branch and bound algorithm. Among those eliminating rules, we find the percentage of nodes eliminated by job incompatible restriction increases as the probability in generating jobs with a family type increases or number of families decreases. Our algorithm can get the optimal solution for the problem with up to 15 jobs, 7 machines and 3 families.

摘要 i
Abstract ii
致謝 iii
Table of Content iv
List of Tables vi
List of Figures vii

Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Problem Description 3
1.3 Research Objectives 4
1.4 Research Methodology and Framework 5
1.4.1 Research Methodology 5
1.4.2 Research Framework 6

Chapter 2 Literature Review 8
2.1 Machine Availability Constraint 8
2.2 Machine Eligibility Constraint 9
2.3 Machine Availability and Eligibility Constraints 10
2.4 Job Incompatible Constraint 12

Chapter 3 Branch and Bound Algorithm 14
3.1 Notations 14
3.2 Bounding Scheme 17
3.2.1 Upper bound 17
3.2.2 Lower bound 21
3.3 Branching Scheme 31
3.3.1 Dominance Rules 33
3.3.2 Branch and Bound Algorithm for the Problem 36

Chapter 4 Computational Analysis 40
4.1 Generating Test Problems 40
4.2 Validation of the Branch and Bound Algorithm 41
4.3 Performance of the Branch and Bound Algorithm 44

Chapter 5 Conclusion 56
5.1 Research Contribution 56
5.2 Research Limitation 56
5.3 Further Research 57

References 58
Appendix 1. Construct Network [adopted from Lin (2006)] 61
Appendix 2. Two-phase binary search algorithm [adopted from Lin (2006)] 63

[1]Azizoglu, M., S. Webster. 2001. Scheduling a batch processing machine with incompatible job families. Computers &Industrial Engineering 39 325-335.
[2]Blazewicz, J., M. Drozdowski, P. Formanowicz, W. Kubiak, G.. Schmidt. 2000. Scheduling preemptable tasks on parallel processors with limited availability. Parallel Computing 26 1195-1211.
[3]Blazewicz, J., P. Dell’Olmo, M. Drozdowski, P. Maczka. 2003. Scheduling multiprocessor tasks on parallel processors with limited availability. European Journal of Operational Research 149 377-389.
[4]Bodlaender, H.L., K. Jansen, and G..J. Woeginger. 1994. Scheduling with incompatible jobs. Discrete Applied Mathematics 55 219-232.
[5]Centeno, G., R.L. Armacost. 1997. Parallel machine scheduling with release time and machine eligibility restrictions. Computers & Industrial Engineering 33(1-2) 273-276.
[6]Centeno, G., R.L. Armacost. 2004. Minimizing makespan on parallel machines with release time and machine eligibility restrictions. International Journal of Production Research 42(6) 1243-1256.
[7]De Reyck, B, W. Herroelen. 1998. A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations. European Journal of Operational Research 111 152-174.
[8]Horn, W.A. 1974. Some simple scheduling algorithms. Naval Research Logistics Quarterly 21 177-185.
[9]Hwang, H.C., S.Y. Chang. 1998. Parallel machines scheduling with machine shutdowns. Computers & Mathematics with Applications 36(3) 21-31.
[10]Hwang, H.C., S.Y. Chang, K. Lee. 2004. Parallel machine scheduling under a grade of service provision. Computers & Operation Research 31 2055-2061.
[11]Hwang, H.C., S.Y. Chang, Y. Hong. 2004. A posterior competitiveness for list scheduling algorithm on machines with eligibility constraints. Asia - Pacific Journal of Operational Research 21(1) 117-125.
[12]Jansen, K. 2003. Approximate strong separation with application in fractional graph coloring and preemptive scheduling. Theoretical Computer Science 302 239-256.
[13]Lee, C.Y. 1991. Parallel machines scheduling with nonsimultaneous machine available time. Discrete Applied Mathematics 30 53-61.
[14]Lee, C.Y. 1996. Machine scheduling with an availability constraint. Journal of Global Optimization 9 395-416.
[15]Lee, C.Y., Y. He, G. Tang. 2000. A note on parallel machine scheduling with non-simultaneous machine available time. Discrete Applied Mathematics 100 133-135.
[16]Liao, L.W., G. J. Sheen. 2007. Parallel machine scheduling with machine availability and eligibility constraints. European Journal Operation Research. Article in press.
[17]Lin, C. F. 2006. Branch and bound algorithm for parallel machine scheduling with availability and eligibility constraints. Unpublished Master Thesis, Institute of Industrial Management, National Central University.
[18]Lin, Y., W. Li. 2004. Parallel machine scheduling of machine-dependent jobs with unit-length. European Journal of Operational Research 156 261-266.
[19]Lu, B. H. 2005. Parallel machine scheduling with machine availability and eligibility constraints. Unpublished Master Thesis, Institute of Industrial Management, National Central University.
[20]Pinedo, M. 2002. Scheduling: Theory, Algorithm and System (2th ed.). Englewood Cliffs, NJ: Prentice-Hall.
[21]Schmidt, G.. 1988. Scheduling independent tasks with deadlines on semi-identical processors. Journal of the Operational Research Society 39 271-277.
[22]Schmidt, G.. 2000. Scheduling with limited machine availability. European Journal of Operational Research 121 1-15.
[23]Sanlaville, E. 1995. Nearly online scheduling of preemptive independent tasks. Discrete Applied Mathematics 57 29-241.
[24]Sheen, G. J., L.W. Liao. 2007. Scheduling machine-dependent jobs to minimize lateness on identical machines with availability constraints. Computers & Operations Research 34 2266-2278.
[25]Ullman, J.D. 1975. NP-complete scheduling problems. Journal of Computer and System Sciences 10 384-393.
[26]Wang, C.S., R. Uzsoy. 2002. A genetic algorithm to minimize maximum lateness on a batch processing machine. Computers &Operations Research 29 1621-1640.
[27]Webster, S., K.R. Baker. 1995. Scheduling groups of jobs on a single machine. Operation Research 43 692-703.