A Hybrid Forward/Backward Approach for Single Batch Scheduling Problems with Non-Identical Job Sizes

融合正向／逆向程序之啓發式演算法求解單機批次加工機台之排程問題

10.29977/JCIIE.200705.0001

王惠梅(Hui-Mei Wang)；張百棧(Pei-Chann Chang)；周富得(Fuh-Der Chou)

批次加工機台 ； 最大完工時間 ； 排程 ； 正向／逆向程序 ； batch processor ； makespan ； scheduling ； forward/backward procedure

工業工程學刊

24卷3期（2007 / 05 / 01）

191 - 199

英文

本文主要係針對單一批次加工機台同時考量工作釋放時間與工作大小的排程問題進行探討，並以最大完工時間最小化做為此排程問題之目標函數。在本文中除了提出可供描述問題與驗證結果正確之混合整數規劃模式之外，並且提出一個融合正向／逆向排程程序觀念之啓發式演算法。透過本研究的實驗結果得知，本文所提出的啓發式演算法在工作數小的問題幾乎均可以在極短的時間內得到最佳解，而針對工作數較大的問題此方法亦可以在合理的求解時間內獲得穩定且不錯的近似最佳解。

This paper considers the single batch scheduling problem with different release times and non-identical job sizes and the objective is to minimize the makespan. A mixed integer programming (MIP) model is developed to describe the complexity of the problem and then a hybrid forward/backward algorithm (HFBA) is developed by moving blocks within an initial schedule to improve the solution quality. Changing the initial schedule at each iteration, HFBA could decrease the influence of the initial schedule and reach the best solution efficiently in the final runs. Extensive experiments show that HFBA can obtain optimal solutions for small-job instances, and have good performances on solution quality for large instances with a modest CPU times.

1. Chandru, V.,C. Y. Lee,R. Uzsoy(1993).Minimizing total completion time on a batch processing machines.International Journal of Production Research,31,2097-2121.
2. Chandru, V.,C. Y. Lee,R. Uzsoy(1993).Minimizing total completion time on a batch processing machines with job families.Operations Research Letters,13,61-65.
3. Chang, P. C.,H. M. Wang(2004).A heuristic for a batch processing machine scheduled to minimise total completion time with non-identical job sizes.International Journal of Advanced Manufacturing Technology,24,615-620.
4. Deng, X.,H. Feng,P. Zhang,Y. Zhang,H. Zhu(2004).Minimizing mean completion time in a batch processing system.Algorithmica,38,513-528.
5. DuPont, L.,C. Dhaenens-Flipo(2002).Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure.Computers & Operations Research,29,807-819.
6. DuPont, L.,F. J. Ghazvini(1997).A branch and bound algorithm for minimizing mean flow time on a single batch processing machine.International Journal of Industrial Engineering,4,197-203.
7. Ghazvini, F. J.,L. DuPont(1998).Minimizing mean flow times criteria on a single batch processing machine with non-identical jobs sizes.International Journal of Production Economics,55,273-280.
8. Gupta, A. K.,A. I. Sivakumar(2005).Single machine scheduling with multiple objectives in semiconductor manufacturing.International Journal of Advanced Manufacturing Technology,26,950-958.
9. Gupta, A. K.,A. I. Sivakumar(2005).Optimization of due-date objectives in scheduling semiconductor batch manufacturing.International Journal of Machine Tools & Manufacturing,46,1671-1679.
10. Lee, C. Y.,R. Uzsoy(1999).Minimizing makespan on a single batch processing machine.International Journal of Production Research,37,219-236.
11. Lee, C. Y.,R. Uzsoy,L. A. Martin-Vega(1992).Efficient algorithms for scheduling semiconductor burn-in operations.Operations Research,40,764-774.
12. Mathirajan, M.,A. I. Sivakumar(2006).A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor.International Journal of Advanced Manufacturing Technology,29,990-1001.
13. Melouk, S.,P. Damodaran,P. Y. Chang(2004).Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing.International Journal of Production Economics,87,141-147.
14. Monch, L.,R. Unbehaun,Y. I. Choung(2006).Minimizing earliness-tardiness on a single burn-in oven with a common due date and maximum allowable tardiness constraint.OR Spectrum,28,177-198.
15. Poon, C. K.,P. Zhang(2004).Minimizing makespan in batch machine scheduling.Algorithmica,39,155-174.
16. Sung, C. S.,Y. I. Choung(2000).Minimizing makespan on a single burn-in oven in semiconductor manufacturing.European Journal of Operational Research,120,559-574.
17. Uzsoy, R.(1994).Scheduling of single batch processing machine with nonidentical job size.International Journal of Production Research,32,1615-1635.
18. Van Der Zee,D. J.(2004).Dynamic scheduling of batch servers with compatible product families.International Journal of Production Research,42,4803-4826.
19. Wang, C. S.,R. Uzsoy(2002).A genetic algorithm to minimize maximum lateness on a batch processing machine.Computers & Operations Research,29,1621-1640.
20. Zhang, G.,X. Cai,C. Y. Lee,C.K. Wong(2001).Minimizing makespan on a single batch processing machine with nonidentical job sizes.Naval Research Logistics,48,226-240.