排程規劃在生管領域中，是極為重要的一個環節。而零工式排程系統又是在排程領域中，最複雜的生產方式。而排程規劃盼能發揮最低存量水準、最少浪費、最少空閒與最適達交，故衍生出時間窗口問題。過去的文獻大多不考慮設置時間，而衡量準則多為總完工時間。若工作有交期限制時，衡量準則是總延遲時間最少，探討的交期限制為一時點。本文將對零工式排程問題進行探討，並把交期限制放寬為一時區，聚焦在於交貨期間內之零工式生產排程之規劃與安排，盼能求得最貼近交期時間下的加工順序，求解最小化庫存成本與延遲成本。
本論文研究主題本質上為NP-hard。本文先對含有時窗限制之零工式排程問題進行數學模式建構，之後進行模擬資料測試，並以C語言撰寫蟻群最佳化程式而求得最好的解，再跟套裝軟體LINGO7.0所求得之最佳解比較蟻群演算法之有效性與健全度。實證結果指出，在有效性與健全度測試上，蟻群演算法具有相當不錯的求解效果，且時效性也比LINGO佳，兼具管理上所講求之效率與效果之意涵。

Scheduling is a very important field in production management. And job shop is a most complex production system on the field. Scheduling operations expect to bring into full play the minimum stock level, wastes, the least idle time and deliver the goods on time, so derive the time window problem. Previous literature regarding job shop scheduling problem (JSP) rarely concerns the machine set-up time, and measure regular is minimizing the tardiness. Here the due date is discussed one point. The study will confer the JSP, and let the due date for an interval. Focusing on scheduling with time window of JSP and expect to get the solution close to the time window. Minimize the total penalty due to the earliness and tardiness.
The property of our study is NP-hard. So we construct the mathematics model for JSP with time window first, and then test the simulate data. The solution got by ant colony optimum (ACO) programs that written by C-language and compare with the best solution gotten by LINGO 7.0 to test the efficiency and robust. The result was pointed out the ACO has good efficiency on the test. And the solving time is less than LINGO. So ACO had both effectiveness and efficiency that stressed on business management.

　錄
目　錄 I
圖目錄 II
表目錄 III
第一章 緒論 1
一、 研究背景與動機 1
二、 研究目的 4
三、 研究範圍 5
四、 研究流程 6
第二章 文獻探討 8
一、零工式排程問題 8
二、時窗限制問題 10
三、蟻群最佳化演算法 12
第三章 研究方法 14
一、 問題描述 14
二、 模型建構 15
三、 蟻群最佳化模式 17
四、 釋例 25
第四章 資料測試 28
一、 測試資料之建立 28
二、 有效性測試 30
三、 健全度測試 33
四、 大型問題模擬測試 36
第五章　結論與建議 38
一、 結論 38
二、 未來研究方向 39
參考文獻 41
一、 中文文獻： 41
二、 英文文獻： 41

參考文獻

中文文獻：
1.江朋南，「蟻群系統在零工式排程問題之應用」，國立台灣科技大學工業管理研究所碩士論文，2003。
2.林依潔，「整合模糊理論與螞蟻演算法於含時間窗限制之車輛途程問題」，國立台北科技大學生產系統工程與管理研究所碩士論文，2003。
3.陳百傑，「以啟發式演算法求解時窗限制車輛途程問題」，中原大學工業工程研究所碩士論文，2002。
4.韓駿逸，「基因演算法解算交貨時區限制零工型排程問題之效果分析」，私立元智大學工業工程研究所碩士論文， 2001。
5.應國卿，「蟻群系統於排程問題之應用」，國立台灣科技大學工業管理系博士論文，2002。
6.魏文鍇，「 利用啟發式演算法求解工單式生產系統排程中時窗限制與釋放時間限制問題」，國立成功大學工業管理科學研究所碩士論文，2003。

英文文獻：
1.Byeon, E. S., Wu, S. D. and Store, R.H., “Decomposition Heuristics for Robust Job-Shop Scheduling,” IEEE Transations on Robotics and Automation, 14(2), 1998, pp.303-313.
2.Blum, C. and Sampels, M., “Ant colony Optimization for FOP Shop scheduling: A case study on different pheromone representation,” Evolutionary Computation, CEC'02, 2002, pp.1558-1563.
3.Carlier, J. and Pinson, E., “An algorithm for solving the job-shop problem,” Management Science, 35, 1989, pp.146-176.
4.Chen, Z. L. and Lee, C. Y., “Parallel machine scheduling with a common due window,” European Journal of Operational Research, 136, 2002, pp.512-527.
5.Gagne, C., Price, W.L. and Gravel, M., “Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times,” Journal of the Operational Research , Society 53, 2002, pp.895-906.
6.Blum, C. and Sampels, M., “ An Ant Colony Optimization for Shop Scheduling Problems,” Journal of Mathematical and Algorithms , 3, 2004, pp.285-308.
7. Dorigo, M., Maniezzo, V. and Colorni, A., “Positive feedback as a search strategy,” Technical Report No. 91-106, 1991, Politecnico di Milano, Italy.
8.Baker, E. K., “An Exact Algorithm for the Time-Constrained Traveling Salesman Problem,” Operations Research Society of America, 31(5), 1983, pp.938-945.
9.Sabuncuoglu, I. and Lejmi, T., “Scheduling for non regular performance measure under the due window approach,” Omega, Int. J. Mgmt. Sci27, 1999, pp.555-568.
10. Bell, J.E. and McMullen, P.R., “Ant colony optimization technique for the vehicle routing problem,” Advanced Engineering Informatics, 18, 2004, pp.41-48.
11. Kuo-Ching Y, Ching-Jong Liao, “ Ant colony system for permutation flow-shop sequencing,” Computers & operation Research, 31, 2004, pp.791-801.
12. Gambardella, L., Taillard, E. and Dorigo, M., “ Ant colonies for the quadratic assignment problem,” Journal of the Operational Research Society, 50, 1999, pp.167-176.
13.Randall, M. and Lewis, A., “A Parallel Implementation of Ant Colony Optimization,” Journal of Parallel and Distributed Computing , 62, 2002, pp.1421-1432.
14.Dorigo, M., Maniezzo, V. and Colorni, A.,“ The Ant System: Optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics–Part B, 26(1), 1996, pp.1-13.
15.Dorigo, M. and Gambardella, L.M., “ Ant colonies for the travelling salesman problem,” Bio systems, 43, 1997, pp.73-81.
16. Maniezzo, V. and Colorni, A.,“The ant system applied to quadratic assignment problem,”IEEE Transactions on Knowledge and Data Engineering, 11, 1999, pp.769-784.
17. Solomon, M.M. and Desrosiers J., “Time Windows Constrained Routing and Scheduling Problem, ”Transportation Science, 22(1) 1,1988, pp.1-13.
18. McMullen, P. R., “An ant colony optimization approach to addressing a JIT sequencing problem with multiple objectives,” Artificial Intelligence in Engineering, 15, 2001, pp. 309－317.
19.Sun, D. and Batta R.,“ Scheduling larger job shops：a decomposition approach,” International Journal of Production Research, 34(7), 1996, pp.2019-2033.
20. Singer, M., “Decomposition methods for large job shops,” Computers & Operations Research, 28, 2001, pp.193-207.
21.Chu, S., Roddick, J.F. and Pan, J.S, “Ant Colony System with Communication Strategies,” Information Sciences, 167, 2004, pp.63-76.
22.Shyua, S.J., Linb, B.M.T. and Yin, P.Y., “Application of ant colony optimization for no-wait flow-shop scheduling problem to minimize the total completion time,” Computers & Industrial Engineering, 47, 2004, pp.181-193.
23. Chu, S.C., Roddick J.F. and Pan, J.S., “Ant colony system with communication strategies,”Information Science, 167, 2004, pp.63-76.
24.T’kindt T., Monmarche, N., Tercinet F. and Laugt, D., “An Ant Colony Optimization algorithm to solve a 2-machine bicriteria flow shop scheduling problem,” European Journal of Operational Research, 142, 2002, pp.250-257.
25.Laarhoven, V., Aarts P. J. M. and Lenstra, J.K., “Job shop scheduling by simulated annealing,” Operations Research, 40, 1992, pp.113-125.
26.Vepsalainen, A. P. J.and Morton, T.E., “Priority rules for job shops with weighted tardiness costs,” Management Science , 33(8), 1987, pp.1035-1047.
27.Zheng, W. X., Nagasawa, H. and Nishiyama, N., “Single-machine scheduling for minimizing total cost with identical, asymmetrical earliness and tardiness penalties,” International Journal of Production Research, 31, 1993, pp.1611-1620.