中文摘要

在分支型的製程系統中，可能會因為其中一分支流程發生不良品，造成重工問題，導致後續作業之存貨堆積或工作等待情形。本文旨在探討分支型流程製程重工的排程問題，以批量重疊方法為基礎，加入時間緩衝量之排程技巧，利用GA演算法決定適當的排程，以TFT-LCD的製造流程為例，來做實務驗證。結果發現利用GA演算法中的meta-search方法，可適當的安排工作順序。在正確位置加入適當的時間緩衝量，可大幅的改善工作延遲時間、工作延遲數目、和工作等待等時間等績效因子，但對機器閒置時間和生產跨距，無明顯的影響。
本研究結果顯示a.對於提升重疊流程型之排程績效而言，使用GA啟發式搜尋法來調整工作排序，是一種最簡易有效且低成本之方法。
b.在分支型生產製程之生產運作中，運用時間緩衝量來決定含重工之工作進度。我們主張採用GA啟發式搜尋法來執行最適化搜尋，是運用進度模擬器來產出適切時間緩衝量為變數，以供GA啟發式搜尋法調整時間緩衝量，去衡量工作進度之績效。c. 未來之研究方向，可朝運用多目標績效衡量因子來評量重疊流程型排程問題。

Abstract
In branched-line flow-shop operations, defects and reworking may result in tardiness, job waiting or idle machines. This study uses an overlap scheduling that involves reworking and a time buffer to enhance system performance for branched-line flow-shop operations. The proposed scheduling solution was applied to a TFT-LCD panel plant as practical demonstration. The results indicate that arranging a job sequence using a meta-search, of which the genetic algorithm-based best-fit search is an appropriate way for improving overlap flow-shop scheduling performance. Improving system performance by setting a suitable time buffer at the right processing step can significantly reduce the time and number of job tardiness, and system job waiting in the illustrative case. However, system machine idles and make span are almost unchanged by the addition of a time buffer.
Analysis results indicate that arranging a job sequence using a meta-search, of which the Genetic Algorithm based best-fit search, is the simplest, effective and least costly way for improving overlap flow-shop scheduling performance. In determining the job schedule involving reworking and a time buffer for branched-line operations, we propose a Genetic Algorithm based overlap scheduling heuristic to perform the best-fit search using a pre-determined time buffer. Having found a suitable time buffer, we build a scheduling simulator to measure the performance for the job schedule that is determined by the Genetic Algorithm when a time buffer is added. The future study may be considered of the theme on the multi-objective for overlap flow-shop scheduling performance.

Keywords： Batch process, flow-shop, genetic algorithm, overlap scheduling, time buffer.

參考文獻
中文文獻

1.張聖麟，卓越化生產管理，第六章時間－競爭階段之四，第五節改善時間競爭能力的方法，華泰書局，1988年(再版)。
2.潘俊明，生產與作業管理，第七章 製程規劃，第二節之產品流動型態與工作重複程度，三民書局，1998年。apdsi@mail.tnit.edu.tw
3.廖麗滿，「塔布搜尋法求解排程問題之研究」國立台灣科技大學工業管理系博士論文，2001。

英文文獻

4.Bahroun, Z., J. P. Campagne and M. Moalla, “Overlapping production plan-ning: A new approach of bounded capacity management,” International Journal of Production Economics, Vol. 64, No. 1-3, pp. 21–36 (2000).
5.Baker, K.R, Introductions to sequencing and scheduling, Wiley: New York (1974).
6.Baker, K.R., “Scheduling groups of jobs in the two-machine flowshop.” Mathmetics Computer Model, Vol. 13, pp. 29–36 (1990).
7.Beenhakke, H.L., Development of alternate criteria for optimality in the ma-chines sequencing problem. Ph.D. Thesis, Purdue University. (1963).
8.Buscher, Udo and Gerd Lindner, “Optimizing a production system with re-work and equal sized batch shipments,” Computer & Operation Research, Vol. 34, pp. 515–535 (2007).
9.Brucker, Peter. And S. Knust, Complexity results for scheduling problems, http://www.mathematik.uni-osnabrueck.de/research/OR/class/
10.Campbell, H.G., R.A. Dudek, and M.L. Smith., “A heuristic algorithm of the n-job, m-machine sequencing problem,” Management Science, Vol. 16, pp.630–637 (1970).
11.Cheng, T.C.E., J.N.D. Gupta, and G, Wang, “A review of flowshop- sched-uling research with set-up times.” Production Operation Management, Vol. 9, pp. 262–282 (2000).
12.Cheng, T.C. and Z. Liu, “3/2-approximation for two-machine no-wait flow-shop scheduling with availability constraints,” Information Process Let-ters, Vol. 88, No. 4, pp. 161–165 (2003).
13. Chr’etienne, P., E.G. Coffman, J. Lenstra and Z. Liu, Scheduling theory and it’s applications, John Wiley & Sons Ltd. (1995).
14.Conway, R.W., W.L. Maxwell and L.W. Miller, Theory of scheduling, Addi-son-Wesley, Reading, MA (1967).
15.Corwin, B.D. and A.O. Esogbue, “Two-machine flowshop-scheduling prob-lems with sequence dependent set-up times: A dynamic programming approach,” Naval Research of Logistic Quartum, Vol. 21, pp. 515–524 (1974).
16.Davis, L., Handbook of genetic algorithms, Van Nostrand Reinhold, New York, (1991).
17.Dorigo, M. and L.M. Gambardella, “Ant colony system: a cooperative learn-ing approach to the traveling salesman problem. IEEE transation on Evolutionary computation, Vol. 1, pp. 53–66 (1997).
18.Fawzan, M. A., and M. Haouari, “A bi-objective model for robust re-source-constrained project scheduling,” International Journal of Production Economics, Vol. 96 No. 2, pp. 175-187 (2005).
19.Gangadharan, R. and C. Rajendran, “A simulated annealing heuristic for scheduling in a flowshop with bicriteria,” Computer and industry engineer-ing, Vol. 27, pp. 473–476 (1994).
20.Glassey, C. R., and G. C. Mauricio, “Closed-loop job release control for VLSI circuit manufacturing,” IEEE Transation, Vol. 1, No.1, pp. 36–45 (1988).
21.Glover, F. and M. Laguna, Tabu Search, (Kluwer: Boston). (1997).
22.Goldberg, D.E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison Wesley, Reading, MA (1989).
23.Goldberg, D.E., Genetic Algorithms in Search, Addison Wesley, Reading, MA (1988).
24.Graham, R.L., E.L. Lawler, J.K. Lenstra, and A.H.G. R.Kan, “Optimization and approximation in deterministic sequencing and scheduling: a survey. Annal.” Discretion of Mathmetics, Vol. 5, pp. 287–326 (1979).
25.Gray. A.E., and Jame Leonard, Process Fundamentals, Harvard Business School, 9-696-023. (DOI: 10.1225/696023) (1995).
26.Gupta, J.N.D., “A functional heuristic algorithm for the flow-shop scheduling problem,” Operation Research, Vol. 22, pp. 39 – 47 (1971).
27.Hall, N.G. and C. Sriskandarajah, “A survey of machine scheduling problems with blocking and no-wait in process.” Operation Research, Vol. 44, pp. 510–525 (1996).

28.Hall, Nicholas G., G. Laporte and C. Sriskandarajah, “Scheduling and lot streaming in flow shops with no-wait in process,” Journal of sheduling, Vol. 6 No.4, pp. 339–354 (2003).
29.Haupt, R., “A srvey of priority rule-based scheduling” Operation Research Spektrum, © Springer-Verlag Vol. 11 pp. 3–16 (1989).
30. Hejazi, S. Reza., and S. Saghafian., “Flowshop-scheduling problems with makespan criterion: a review” International Journal of Operation Research, Vol. 43, No. 14, 15 July 2005, pp. 2895–2929 (2005).
31.Heizer, Jar and Barry Render, Principles of Operations Management, 5th Ed. Pearson Education, Inc., Prentice Hall (2004).
32. Holland, J. H., Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor. (1975).
33. Ishibuchi, M., S. Misaki, and H. Tanaka, “Modified simulated annealing for the flow shop sequencing problems.” European Journal of Operational Re-search, Vol. 81, pp. 388–398 (1995).
34. Li, Heng., Li. Zhicheng, X. Li. Ling, and Bin Hu, “A Production Resched-uling Expert Simulation System,” European Journal of Operational Research, Vol. 124, pp. 283–293 (2000)
35. Meredith, Jack R and Scott M. Shafer., Operations Management for MBA, 2nd Ed., Wake Forest University, John Wiley & Sons, Inc. (2001)
36. Johnson, S.M., “Optimal two- and three-stage production schedules with set-up times included,” Naval Research of Logistic Quartum, Vol. 1, pp. 61– 68 (1954).

37. Lann, A., G. Mosheiov and Y. Rinott, “Asymptotic optimality in probability of a heuristic schedule for open shops with job overlaps,” Operation Re-search Letters, Vol. 22, No. 2-3, pp. 63 – 68 (1998).
38. Lee, C.Y., T.C.E. Cheng and B.M.T. Lin, “Minimizing the makespan in the 3-machine assembly-type flowshop-scheduling problem,” Management Sci-ence, Vol. 39, pp. 616 – 625 (1993).
39. Leisten, R., “Flow-shop Sequencing Problems with Limited Buffer Storage,” International Journal of Production Research, Vol. 28, pp. 2085–2100 (1990).
40. Little, J.D.C., “A proof for the queuing formula: L = λ • W,” Operations Research, Vol. 9, pp. 383–397 (1961).
41. Mellor, P., “A review of Job Shop Scheduling” Operation Research Quar-terly, Vol. 17, No2, pp.161– 170 (1966).
42. Murata, T., H. Ishibuchi, and H. Tanaka, “Multi-objective genetic algorithm and its applications to flowshop-scheduling.” Computer and Industry Engi-neering, Vol. 30, pp. 957–968 (1996)
43. Nawaz, M., E. Enscore Jr, and I. Ham, “A heuristic algorithm for the m-machine, n-job flowshop sequencing problem.” OMEGA, International Journal of Management Science, Vol. 11, pp. 91–95 (1983)
44. Ogbu, F.A. and D.K. Smith, “Simulated annealing for the permutation flowshop problem.” OMEGA, International Journal of Management Science, Vol. 19, pp. 64–67 (1991).
45. Panwalkar, S. S., and W. Iskander, “A survey of scheduling rules” Opera-tions Research, Vol. 25, No.1, pp. 45–61 (1977).
46. Palmer, D.S., “Sequencing jobs through a multistage process in the minimum total time: A qick method of obtaining a near optimum,” Operation Research Quarterly, Vol. 16, pp. 101–107 (1965).
47 Pinedo, Michael and Xiuli Chao, Operations Scheduling with Applications in Manufacturing and Services, McGraw Hill, (2000).
48. Pinedo, Michael, Scheduling, Theory, Algorithms, and Systems, 2nd Ed., Prentice Hall, (2002).
49. Pinedo, Michael, Scheduling Theory, Algorithms, and Systems, Columbia University, Pearson Education, Inc., Prentice Hall (1995).
50. Panwalwer, S. S., and W. Iskander, “A survey of scheduling rules” Operation Research, Vol. 25, No. 1, Jan-Feb (1977).
51. Ponnambalam, S.G., P. Aravindan and S. Chandrasekaran, “Constructive and improvement flowshop-scheduling heuristics: An extensive evaluation,” Pro-duction Planning and Control Journal, Vol. 12, pp. 335–344. (2001).
52. Reeves, C. and T. Yamada, “Genetic algorithms, path relinking, and the flowshop sequencing problem.” evolution computer, Vol. 6, pp. 45–60 (1998).
53. Reeves, C.R., “Improving the efficiency of tabu search for machine schedul-ing problems.” Journal of the Operational Research Society, Vol. 44, pp. 375–382 (1993).
54. Ruiz, R., C. Maroto, and J. Alcaraz, “Solving the flowshop-scheduling prob-lem with sequencedependent set-up times using advanced metaheuristics.” European Journal of Operational Research, (2004) .

55. Sinclair, Bart, 2007 Little’s Theorem =λ × , http://cnx.org/content/m10747/latest/
56. Sisson, Roger L., Methods of squencing in job shops---A review management sciences research project, University of California, Los Angeles, California pp.10–29 (1958).
57. Sriskandarajah, C. and E. Wagneur, “Lot streaming and scheduling multiple products in two-machine no-waitflow-shops,” AIIE Transation, Vol. 31, No. 8, pp. 695–707 (1999).
58. Subodha, Kumar, T. P. Bagchi and C. Sriskandarajah, “Lot streaming and scheduling heuristics for m-machine no-wait flow shops,” Computer and in-dustry engineering, Vol. 38 No.1, pp. 149–172 (2000).
59. Wagneur, E. and C. Sriskandarajah, “Open shops with jobs overlap,” Euro-pean Journal of Operational Research, Vol. 71, No. 3, pp. 366–378 (1993).
60. Wang, L. and D.Z. Zheng, “An effective hybrid heuristic for flow-shop scheduling.” International Journal of Advanced Manufacturing Technology, Vol. 21, No. 1, pp. 38–44 (2003)