具機器可用時間與機器合適度限制和相依整備作業之平行機台排程問題

An Identical Parallel-Machine Scheduling Problem with the Consideration of Machine Availability, Eligibility and Dependent Setup Time

江曜君(Yao-jun Jiang)

指導教授 ： 沈國基

國立中央大學/管理學院/工業管理研究所/碩士(2011年)

摘要

在此研究中，我們考慮當極小化總作業之完工時間時，在具機器可用時間與機器合適度且整備作業相依化的限制下，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.

並列關鍵字

machine eligibility ； dependent setup time ； total completion time ； parallel machine ； branch and bound algorithm ； machine availability ； non-preemptive jobs

參考文獻

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.