臺灣博碩士論文加值系統

大多數的排程研究均以機器在規劃期間可持續加工為主要假設條件之一，可是在實務上，這個條件往往是不成立的。機器經常會由於某些原因而必須停止，無法持續加工，有些因素是可預期的，如：定期保養、固定維修等，而有些因素是不可預期的，如：突發性的故障等。
本研究假設有兩部平行機台，其中一部機台在某一段時間中無法使用，而這段時間固定且事先預知，原因可能是這個機台需要定期保養或固定維修。衡量準則是求取最大完工時間最小化，而工件的型態也被區分為可中斷與不可中斷兩種類型。
本研究分別針對工件可中斷與不可中斷兩種型態，分別將各問題分為四種情形，針對每種情形提出適當的演算法來產生最佳解。雖然每個演算法皆具指數分配的時間複雜度，但驗證後發現，即使大型問題，如：100個工件，這些演算法都能夠在相當短的時間中求得最佳解。

In the paper, we consider a two-parallel-machine problem where one machine is not available during a time period. The unavailable time period is fixed and known in advance. A machine is not available probably because it needs preventive maintenance or periodical repair. The objective of the problem is to minimize the makespan. For both nonresumable and resumable cases, we partition the problem into four sub-problems, each of which is solved optimally by an algorithm. Although all the algorithms have exponential time complexity, they are quite efficient in solving large-sized problems.

Chinese Abstract i
English Abstract ii
Ackowledgement iii
Contents iv
Figure Index vi
Table Index vii
Chapter 1. Introduction 1
Chapter 2. Literature Review 2
Chapter 3. The Nonresumable Case 5
3.1. Problem Complexity 5
3.2. Problem Assumptions and Notations 5
3.3. Problem Analysis 6
3.4. Algorithms 8
3.4.1. The TMO Algorithm 8
3.4.2. Case 1. 8
3.4.3. Case 2 9
3.4.4. Case 3 9
3.4.5. Case 4 13
Chapter 4. The Resumable Case 19
4.1. Problem Analysis 19
4.2. Algorithms 19
4.2.1. Case 1 19
4.2.2. Case 2 19
4.2.3. Case 3 20
4.2.4. Case 4 21
Chapter 5. Experimental Result 22
Chapter 6. Conclusion 28
Appendix A. The TMO Algorithm 32
Author 35
Authority 36

[1] Adiri, I., Bruno J., Frostig E., and A.H.G. Rinnooy Kan,
Single machine flow-time scheduling with a single
breakdown,” Acta Informatica, Vol. 26, pp. 679-696 (1989).
[2] Ho J.C. and J.S. Wong, “Makespan minimization for m
parallel identical processors,” Naval Research Logistics,
Vol. 42, pp. 935-948 (1995).
[3] Lee C.Y., “Parallel machine scheduling with
nonsimultaneous machine available time,” Discrete Applied
Mathematics, Vol. 30, pp. 53-61 (1991).
[4] Lee C.Y. and S.D. Liman, “Single machine flow-time
scheduling with scheduled maintenance,” Acta Informatica,
Vol. 29, pp. 375-382 (1992).
[5] Lee C.Y. and S.D. Liman, “Capacitated two-parallel
machines scheduling to minimize sum of job completion
times,” Discrete Applied Mathematics, Vol. 41, pp. 211-222
(1993).
[6] Lee C.Y., “Machine scheduling with an availability
constraint,” Journal of Global Optimization, Vol. 9, pp.
395-416 (1996).
[7] Lee C.Y., “Minimizing the makespan in the two-machine
flowshop scheduling problem with an availability
constraint,” Operational Research Letter, Vol. 20, pp. 129-
139 (1997).
[8] Lee C.Y. and L. Lei, M. Pinedo, “Current trends in
deterministic scheduling,” Annals of Operational Research,
Vol. 114, pp. 420-429 (1997).
[9] Lee C.Y., “Two-machine flowshop scheduling with an
availability constraint,” European Journal of Operational
Research, Vol. 114, pp. 420-429 (1999).
[10] Lee C.Y., Y. He, and G. Tang, “A note on parallel machine
scheduling with nonsimultaneous machine available time,”
Discrete Applied Mathematics, Vol. 100, pp. 133-135 (2000).
[11] Lenstra J.K., K. A.H.G. Rinnooy, and P. Brucker,
“Complexity of machine scheduling problems,” Annals of
Discrete Mathematics, Vol. 1, pp. 342-362 (1997).
[12] Schmidt G., “Scheduling independent tasks with deadlines
on semi-identical processors,” Journal of Operational
Research Society, Vol. 39, pp. 271-277 (1984).
[13] Schmidt G., “Scheduling with limited availability,”
European Journal of Operational Research, Vol. 121, pp. 1-
15 (2000).