摘要
一般流程式加工是指工件必須在第一工作站完成後，才允許進入第二工作站，而所謂的不完全作業是指有部分工件不需在第一工作站加工，可直接進入第二工作站進行加工。本研究建構在不完全作業(missing operations)下兩工作站混合流程式排程，在機台的分配上分別是第一工作站為單一機台，第二工作站為兩部相同之平行機台。求解此問題之總完工時間(total completion time)。
本研究先建立數學模式之方式求解上述之問題，由於此數學模式之限制式為非線性不等式，當工件數量龐大時，Lingo 9.0求出的解無法保證是最小化總完工時間。除此之外，總完工時間之兩工作站流程問題，若有任一個工作站超過一部機台且小於工件數量之情形下，可視為NP-hard問題。因此本研究建立四種啟發式演算法來求此問題之近似最佳解，第一個啟發式演算法為工件在兩工作站相同加工順序之排程，第二個啟發式演算法為工件在第一工作站加工時間之最短加工時間法(SPT)排序第一工作站之排程，接著排序第二工作站之工件。第三個啟發式演算法為工件在第一工作站與第二工作站相加之加工時間，並依最短加工時間法(SPT)排序第一工作站之排程，第四個啟發式演算法為工件在第一工作站與第二工作站相乘之加工時間，並依最短加工時間法(SPT)排序第一工作站之排程，接著排序第二工作站之工件。根據求解工件數之大小，不完全作業百分比與加工時間不同的資料設定下，比較四種啟發式演算法所求出的解。
最後根據分析之結果，當工件不完全百分比為10%與20%，兩工作站之工件加工時間變異性相同，適合啟發式演算法2求解，而變異性不同時，適合啟發式演算法3或演算法4求解。當工件不完全百分比為40%，不論兩工作站之工件加工時間變異性是否相同，啟發式演算法3或演算法4可得到較小總完工時間。

關鍵字: 流程式排程、不完全作業、總完工時間

Abstract
The scheduling problem in a hybrid flowshop has been the subject of considerable research. All the studies on this subject assume that each job has to be processed on all the stages. However, missing operations usually exist in many real-life production systems. For example, a two-stage system, some jobs have to be processed on both stages, but others need only to be processed on the second stage. This study focuses on a two-stage hybrid flowshop scheduling with missing operations. The studied production system in the factory is composed of two stages in series. The first stage contains only one machine while the second stage consists of two identical machines (namely a 1×2 hybrid flowshop). Four heuristics are developed to solve the problem with the objective of minimizing the total completion time.
This research develops a mathematical model with non-linear constrains to solve the problem. When the number of jobs is huge, we can’t promise to find the scheduling that minimizing total completion time by Lingo 9.0. Furthermore, the problem becomes NP-hard if any of the two stages contains more than one machine. Consequently, four heuristics are developed to solve the problem. The first heuristic generates a permutation schedule. The second heuristic generates a non-permutation schedule by the shortest processing time (SPT) rule according to the processing time at stage 1. The third heuristic generates a non-permutation schedule by the SPT rule according to the total processing time of both stages. The fourth heuristic generates a non-permutation schedule by the SPT rule according to the product of the two stages’ processing times.
Based on the numerical result, if the percentages of missing operations are 10% and 20% and the variances of processing times at two stages are the same, the second heuristic generated better solutions. Otherwise, the third heuristic and the fourth heuristic are better. If the percentages of missing operations are 40%, the third heuristic and the fourth heuristic are better.

Keywords: flowshop scheduling, missing operations, total completion time

參考文獻
中文部分:
1. 石育榤，動態平行機雙準則排程啟發式演算法之研究，國立台灣科技大學工業管理所碩士論文，民國94年。
2. 田國興，有設置時間之流程式工廠多工作站平行機台總排程時間最小化問題，私立中原大學工業工程所碩士論文，民國88年。

英文部分:
1. Adiri, I., & Pohoryles, D., 1982. Flowshop/No-idle or no-wait scheduling to minimizing the sum of completion time. Naval Research Logistics Quarterly, 29, 495-504.
2. Ahmadi, R.H., & Bagchi, U., 1990. Improved lower bounds for minimizing the sum of completion times of n jobs over m machines in a flow shop. European Journal of Operational Research, 44, 331–336.
3. Arthanary, T.S., Ramaswamy, K.G., 1971. AN extension of two machine sequencing problem. Opsearch, 8, 10–22.
4. Bansal, S.P., 1977. Minimizing the sum of completion times of n-jobs over M-machines in a flowshop. AIIE Transactions, 9, 306-311.
5. Ben Daya, M., & Al-Fawzan., 1998. A tabu search approach for the flowshop scheduling problem. European Journal of Operational Research, 109, 88–95.
6. Campbell, H. G., Dudek, R. A., Smith, M. L., 1970. A heuristic algorithm for the N-job, m-machine sequencing problem. Management Science, 16, B630–B637.
7. Dannenbring, D. G., 1977. AN evaluation of flow-shop sequencing heuristics. Management Science, 23, 1174–1182.
8. Garey, M.R., Johnson, D.S., Sethi, R., 1976. Complexity of flowshop and jobshop scheduling. Mathematics of Operation Research, 1, 117-129.
9. Gupta, J. N.D., 1988. Two stage, hybrid flowshop scheduling problem. Journal of the Operational Research Society, 39, 359–364.
10. Gupta, J.N.D., Tunc, E.A., 1991. Schedules for a two-stage hybrid flowshop with parallel machines at the second stage. International Journal of Production Research, 29, 1489–1502.
11. Hariri, A.M.A., Potts, C.N., 1997. A branch and bound algorithm for the two-stage assembly scheduling problem. European Journal of Operational Research, 103, 547–556.
12. Ho, J.C., 1995. Flowshop sequencing with Mean flow time objective. European Journal of Operational Research, 81, 571-578.
13. Ignal, E., Schrage, L., 1965. ApplicatioN of the braNch-and-bouNd techNique to some flowshop scheduling problems. Operation Research, 13, 400-412.
14. Ishibuchi, H., Misaki, S., Tanaka, H., 1995. Modified simulated annealing algorithm for the flow-shop sequencing problems. European Journal of Operational Research, 81, 388–398.
15. Kim, D.W., Na, D.G., Chen, F.F., 2003. Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective. Robotics and Computer Integrated Manufacturing, 19, 173–181.
16. Koulamas, C., Kyparisis, G.J., 2001. The three stage assembly flowshop scheduling problem. Computers and Operations Research, 28, 689–704.
17. Leung, J.Y., Li, H., Pinedo, M., Zhang, J., 2007. Minimizing total weighted completion time when scheduling orders in a flexible environment with uniform machines. Information Processing Letters, 103, 119–129.
18. Liao, C.J., & Lin, C.H., 2003. Makespan minimization for two uniform parallel machines. I International Journal of Production Economics, 84, 205–213.
19. Mellouli, R., Sadfi, C., Chu, C., Kacem, I., 2009. Identical parallel-machine scheduling under availability constraints to Minimize the sum of completion times. European Journal of Operational Research, 197 1150–1165.
20. Miyazaki, S., Nishiyama, N., Hashimoto, F., 1978. AN adjacent pairwise approach to the Mean flow-time scheduling problem. Journal of the Operation Research Society of Japan, 21, 287-299.
21. Nawaz, M., Enscore, E.E., Ham I., 1983. A heuristic algorithm for the m-machine, N-job flowshop sequencing problem. OMEGA, 11, 91–95.
22. Ogbu, F. A., & Smith, D. K., 1990. The application of the simulated annealing algorithm to the solution of the N/m/Cmax flowshop problem. Computers and Operations Research, 17, 243–253.
23. Pinedo, M.L., 2008. Scheduling theory, algorithms, and system. Springer, New York, NY.
24. Potts, C.N., Sevast’janov, S.V., Strusevich, V.A., Van Wassenhove, L.N., Zwaneveld, C.M., 1995. The two-stage assembly scheduling problem: Complexity and approximation. Operations Research, 43 (2), 346–355.
25. Pugazhendhi, S., Thiagarajan, S., Rajendran, C., Anantharaman, N., 2002. Performance enhancement by using non-permutation schedules in flowline-based manufacturing systems. Computers and Industrial Engineering, 44, 133–157.
26. Rajendran, C., 1993. Heuristic algorithm for scheduling in a flowshop to Minimize total flow time. International Journal of Production Economics, 29, 65-73.
27. Rajendran, C., Ziegler, H., 2001. A performance analysis of dispatching rules and a heuristic in static flowshops with missing operations of jobs. European Journal of Operational Research, 131, 622-634.
28. Sung, C.S., Kim, H.A., 2008. A two-stage multiple-machine assembly scheduling problem for Minimizing sum of completion times. International Journal of Production Economics, 113, 1038–1048.
29. Taillard, E., 1990. Some efficient heuristic methods for the flowshop sequencing problem. European Journal of Operational Research, 47, 65–79.
30. Tseng, C.-T., Liao, C.-J., Liao, T.-X., 2008. A Note on two-stage hybrid flowshop scheduling with missing operations. Computers & Industrial Engineering, 54 695–704.
31. Widmer, M., Hertz, A., 1989. A New heuristic method for the flowshop sequencing problem. European Journal of Operational Research, 41, 186–193.