臺灣博碩士論文加值系統

在此研究中，我們考慮當極小化總作業之完工時間時，在具機器可用時間與機器合適度且整備作業相依化的限制下，n個不可分割的工作和m台等效平行機台的排程問題。每台機器只有某些時間區段可以被安排處理工作，每個工作也只能被安排在某些特定的機器上，而每當我們欲服務工作時其必須先執行一個整備作業好讓機台的生產環境符合此工作的需求，而此整備作業的執行時間則是由此機台的前續作業與接下來要服務的作業種類來決定的，因此我們才會稱此整備作業為相依的。
在此我們提出一個分枝界限演算法去尋找這個問題的最佳解。首先，我們修改Liao & Sheen (2007)切割時間區間的方式，將時間區間以各機台獨立的方式去做切割，再者我們將欲規劃的各工作視為不能分割的情況下去提出下界值的計算方式，最後我們提出分枝的方式與減少分枝不必要分枝的方法。而我們所提出的
方法透過我們設計的實驗可以發現兩件事情。第一我們可以發現當問題環境於機器總數相同的情況下，當我欲處理較多的工作時，倘若我們使用相依方式處理時間區間時將使得其獲得最佳解的時間與使用獨立切割時間區間的方法來的長的許多。第二，我們也可以發現當預處理的問題越大時，其下界的刪除無用的分枝效率會越來越高。

In this thesis, we consider the problem of scheduling n non-preemptive jobs on m identical machines with machine availability, eligibility and dependent setup time. The problem comes from industrial applications. Each machine is not continuously available at all time and each job is only allowed to be processed on specific machines. Dependent setup is that the setup time is determined not only by that job but also by the previous job. Then we hope we will develop an efficient algorithm to solve this problem.
First, we focus on our constraint, machine availability to modify the method used in Liao & Sheen (2007) to deal with it. We divide all time epochs on each machine independently and look forward to spend less time getting our solution. Then we propose our lower bound. It doesn’t apply the usual way seem all jobs are preemptive to calculate the value of bound. I still think our jobs are not preemptive to get a value closing the actual situation. Besides, we propose branching schema, propositions and dominance rules to construct our branch and bound algorithm. Finally, through our experiment we could realize the performance of our lower bound and the decision of dealing with machine availability. We find that when the problem size becomes bigger and bigger, the lower bound we proposed can help us cut more and more meaningless bounds. Similarly, we also can find that on the same machine size when
III
we want to solve the problem with more and more jobs, we have to spend much time calculating it. On the other hand, we finally propose some comments and limitations of the studied problem in the end of the thesis.

Table of Content
Abstract II
Table of Content V
List of Tables VII
List of Figures VIII
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Problem Description 2
1.3 Research objectives 3
1.4 Research Methodology and Frame Work 4
1.4.1 Research Methodology 4
1.4.2 Research Framework 4
Chapter 2 Literature review 6
2.1 Machine Availability Constraint 6
2.2 Machine Eligibility Constraint 7
2.3 Dependent setup time Constraints 7
Chapter 3 Algorithm for 9
3.1 Notations 9
3.2 Obtaining the time epoch set E and determining the time interval 10
3.3 Branching and Bound Algorithm for the Problem 12
3.3.1 A lower bound for the problem 12
3.3.2 Branching Scheme 15
3.3.3 Dominance Rules 20
3.3.4 Branch and Bound Algorithm for the Problem 23
Chapter 4 Computational Analysis 30
4.1 Test Problem Generation 30
4.2 Test Problem Optimally 31
4.3 Test Problem Efficient 34
5.1 Research Contribution 39
5.3 Further Research 40
Appendix.1 44
An example of for Branch and Bound Algorithm 44

1. Brucker, P., & Kravchenko, S. A. (2008). Scheduling jobs with equal processing times and time windows on identical parallel machines. Journal of Scheduling (11), pp. 4229-237.
2. Chartrand, G. (1985). Introductory Graph Theory, New York, Dover Pubns.
3. Chen, W. J. (2006). Minimizing total flow time in the single-machine scheduling problem with periodic maintenance. Journal of Operational Research Society (57), pp. 10–415.
4. Chen, W. (2009). Scheduling with dependent setups and maintenance in a textile company. Computers & Industrial Engineering (57), pp. 867–873.
5. Chen, Z.L. & Powell, W. (2003). Exact algorithms for scheduling multiple families of jobs on parallel machines. Naval Research Logistics (50), pp. 823–840.
6. Lee, A., Huang, C. & Chung, S. (2007). Minimizing the Total Completion Time for the TFT-Array Factory Scheduling Problem (TAFSP) . Lecture Notes in Computer Science (4705), pp. 767-778.
7. Lee, W., Lin, Y. & Wu, C. (2010). A branch and bound and heuristic algorithm for the single-machine time-dependent scheduling problem. The International Journal of Advanced Manufacturing Technology (47), pp. 1217–1223.
43
8. Liao, L., & Sheen, G. (2007). Parallel machine scheduling with machine availability and eligibility constraints. European Journal of Operational Research (184), pp. 458–467.
9. Lin, C. F. (2006). Branch and bound algorithm for parallel machine scheduling with availability and eligibility constraints. Institute of Industrial Management, National Central University.
10. Li, Y. W. (2004). Parallel machine scheduling of machine-dependent jobs with unit-length. European Journal of Operational Research (156), pp. 261-266.
11. Mosheiov, G. (1994). Minimizing the sum of job completion on capacitated parallel machines. Mathematical and Computer Modeling (20), pp. 91–99.
12. Nessah, R. (2007). An exact method for problem. Computers & Operations Research (34), pp. 2840 – 2848.
13. Nessah, R., Yalaoui, F., & Chu, C. (2008). A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates. Computers & Operations Research (35), pp. 1176 – 1190.
14. Pinedo, M. (2002). Scheduling: Theory, Algorithm and System (2th ed). New York: Prentice-Hall.