臺灣博碩士論文加值系統

排程（scheduling）是生產管理裡面一個重要的分枝，主要探討生產製造商如何將有限的資源（不論是機台、整備資源、人員）在特定的時間運用於工作上，以達到最大的目標效益。而現今製造商所面臨的問題即是顧客需求快速變動，產品一代接著一代快速的替換，過去只要大量製造產品就能賺錢的觀念已不復存在。因此，若能考量到產線各種可能的實際情況，舉凡說，因為產品生命週期縮短，而導致生產線在短時間內就要更換機台設備所產生的整備時間（setup time）；為了縮短工作加工時間，許多製造廠會藉著訓練員工以提升學習效應（learning effect）；整體供應鏈來說，廠商的信譽極其重要，為了不能讓產品延遲太久或庫存太多，而考慮的時間窗口（time windows）等等因素，將以上因素整合到排程模型中，並將工作排程做最好的規劃，藉此降低生產成本，提高生產效率，維持廠商信譽。
為此，本研究將發展一考量整備時間、學習效應與時間窗口之單機排程模型，以總懲罰成本為排程績效指標，並建構分枝界限、啟發式演算法與基因演算法，藉著模擬工作數據來測試此演算法之準確度與運算效率，希冀測試結果能夠提供管理決策者以及往後研究之參考。

Scheduling is an important part of production management. Its purpose is to make full use of limited resource and to achieve maximum benefits for manufacturers. Currently, manufacturers are facing the problems regarding the ever-changing customer demands and product’s phase in and out generation after generation. Thus the concept of mass-produced products does not exist anymore.
Therefore, there will be higher chance that cost can be lowered and production process will be more efficient if some practical factors are taken into consideration. For example, shorter product life cycle will lead to shorter setup time. And the processing time can be shorten by applying appropriate training of employees. Furthermore, there is possibility that a best plan will be made and results in lower cost and higher efficiency if above factors are taken into account.
This research develops a single-machine scheduling model that involves the factors such as setup time, learning effect and time windows. The total punishment cost is the indicators of scheduling performance. The psuedo Branch and Bound Algorithm, Heuristic Algorithm and Genetic Algorithm are used in this research. Data simulation is used for testing the accuracy and computational efficiency of this algorithm. The results of the research are to help decision-makers making better decisions and provide reference for their further researches.

目錄
摘要 II
Abstract III
致謝 IV
目錄 V
圖目錄 VII
表目錄 VIII
第一章　緒論 1
第一節　研究動機 1
第二節　研究目的 1
第三節　研究範圍與限制 2
第四節　研究流程與架構 2
第五節　論文大鋼 3
第二章　文獻探討 4
第一節　排程理論 4
第二節　整備時間 6
第三節　學習效應 7
第四節　時間窗口 8
第五節　分枝界限法 10
第六節　基因演算法 12
第七節　小結 15
第三章　單機生產排程中整備時間、學習效果與時間窗口問題 16
第一節　問題定義與基本假設 16
第二節　考量整備時間之單機排程原始模型 17
第三節　加入學習效果與時間窗口之單機排程模型 21
第四節　考量整備時間、學習效果與時間窗口之單機生產排程問題 26
第五節　小結 33
第四章　實例驗證與分析 35
第一節　測試資料產生 35
第二節　基因演算法參數分析 38
第三節　演算法求解評比 44
第四節　敏感度分析 48
第五節　小結 53
第五章　結論與建議 55
第一節　結論 55
第二節　未來研究建議 56
參考文獻 57

林秋萍，2009，不同啟發式演算法應用於考量整備時間之單機排程問題之比較，國立成功大學工業與資訊管理所碩士論文

Bagchi. U., Y. Chang and R. Sullivan, (1987) Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date, Naval Res. Logist. Quart. 34 pp.739-751.

Biskup, D.(1999) Single-machine scheduling with learning considerations, European Journal of Operational Research, Vol 115, pp.173-178.

Brooks, G.H. and White, C.R. (1965), An Algorithm for Finding Optimal or Near Optimal Solutions to the Production Scheduling Problem. Journal of Industrial Engineering, Vol. 16, No.1, pp.34-40.

Chen, Z. L. and Lee, C. Y. (2002) Parallel machine scheduling with a common due window. European Journal of Operational Research, Vol. 136, pp. 512-527.

Chris N. Potts, Mikhail Y. Kovalyov. (2000) Scheduling with batching: A review, European Journal of Operational Research.

Feng Jin, Shiji Song, Cheng Wu.(2009) A simulated annealing algorithm for single machine scheduling problems with family setups.Computers ＆ Operations Research, Vol.36 pp.2133-2138

Graham, R. L., E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan. (1979) Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematic, Vol 5 pp.287-326.

Gen, M., R. Cheng.（1997）Genetic Algorithm and Engineering Design, John Wiley ＆ Sons, Inc.

J. Heizer, B. Render, (2001) Operations Management, sixth ed., Prentice-Hall.

Kenneth R. Baker and Gary D. Scudder (1990) Sequencing with Earliness and Tardiness Penalties : A Review. Operations Research, Vol.38, No.1, pp22-36.

Liao, Ching-Jong, and Li-Man Liao. (1997) Single Facility Scheduling with Major and Minor Setups. Computers ＆ Operations Research Vol 24, No.2, pp.169-178.

Lawler, E.L., (1977) A Pseudo-Polynomial Algorithm For Sequencing Jobs To Minimize Total Tardiness., Annals Of Discrete Mathematics, 1, pp.331-342.

Ling Huey Su and Yi-Yu Tien, (2011) Minimizing mean absolute deviation of completion time about a common due window subject to maximum tardiness for a single machine. Int. J. Production Economics, Vol.134, pp196-203.

Mosheiov, G. (2001) Scheduling problems with a learning effect, European Journal of Operational Research, Vol 132, pp.687-693.

Pinedo, M. (1995) Scheduling, Prentice Hall.

Sabuncuoglu, I. and Lejmi, T. (1999) Scheduling for non regular performance measure under the due window approach. Omega, The International Journal of Management Science, Vol. 27, pp.555-568.

Tan K.C., R Narasimhan, P.A. Rubin, G.L. Ragatz, (2000) A comparison of four methods for minimizing total tardiness on a single processor with sequence dependent setup times, Omega, The International Journal of Management Science Vol 28 pp.313-326.

Wen-Chiung Lee and Chin-Chia Wu and Peng Hsiang Hsu, (2010) A single machine learning effect scheduling problem with release times. Omega, The International Journal of Management Science, Vol 38 pp.3-11.

Wright, T.P. (1936) Factors affecting the cost of airplanes. Journal of Aeronautical Science, Vol 3, pp.122-128.

Yano,C.A., and Kim, Y.D., (1991) Algorithms for a class of single machine weighted tardiness and earliness problems, European Journal of Operational Research Vol 52 pp.167-178.