Abstract
For cutting department in an apparel factory, the first priority is to satisfy sewing operation which is the bottleneck in manufacturing and need cut pieces from cutting department. Each fabric lay in cutting department can cut out the garment pieces in different sizes and different colors. In order to avoid idle situation in sewing operations, the cutting department should determine appropriate finish cutting time of each fabric lay to satisfy sewing operations in time. Since the difficulty of managing cut pieces, the cutting department would also like to decrease the inventory of cut pieces. Therefore, the problem in this study focus on determine the ideal finish cutting time for each fabric lays to satisfy sewing operation in time and minimize the inventory of cut pieces.
This study proposed a mixed integer programming model and a heuristic method to solve such a cutting schedule problem in apparel factory. We take satisfying sewing operation as constraint, and set the objective as minimizing the inventory of cut pieces. The experiment result shows the mixed integer programming model and heuristic method both has good performance while under small problems. The solution solved by heuristic method is not as good as by mixed integer program while in medium and large problem. However, since the mixed integer programming model requires longer time when solving medium and large problem; thus, the heuristic method is recommended to use.

Keywords: apparel manufacturing; cutting operation; cutting production scheduling; mixed integer programming.

摘要
對於在成衣工廠的裁切製程而言，其首要目標為滿足下游的車縫製程；因車縫製程是成衣工廠的瓶頸製程，故裁切部門必須確保裁切製程所裁出的半成品能及時送到車縫製程進行加工。在裁切部門中，一個裁切床可以裁出許多不同尺寸、不同顏色的衣服零件，也就是半成品；而為了避免車縫製程因缺少半成品而出現閒置的情況，所以裁切部門必須對各裁切床決定適當的裁切時間，以確保車縫製程的需求皆能被滿足。而由於裁切出的半成品為片狀的衣服零件，管理半成品庫存不易，故裁切部門也希望能降低其半成品的庫存量。因此，此篇論文將考慮如何為各裁切床決定出理想的裁切完工時間以滿足車縫製程的需求，同時還能降低裁切部門的半成品庫存量。
本篇論文中針對在成衣工廠中出現的裁切製程排程問題，提出一個混整數的求解模型以及一個啟發式的求解方法來幫助解決問題。本篇論文將滿足車縫線需求視為限制式，並將最小化半成品庫存量當作目標式。由實驗結果顯示，混整數模型與啟發式求解法在小型問題時皆有很好的求解績效；而在中、大型問題時，雖然啟發式求解法的求解不如混整數模型來得好，但考慮到混整數模型在解中、大型問題時需要很長的求解時間，故求解中、大型問題時，仍推薦使用啟發式求解法。

關鍵字：成衣業；裁切製程；裁切生產排程；混合整數規劃

TABLE OF CONTENTS
摘要 I
Abstract II
TABLE OF CONTENTS III
LIST OF TABLES IV
LIST OF FIGURES V
1. Introduction 1
1.1. Introduction for Apparel Manufacturing 1
1.2. Problem Definition and Assumptions 7
2. Literature Review 9
3. Approaches 12
3.1. Mixed Integer Programming Model 12
3.1.1. Notation 12
3.1.2. Model Formulation 13
3.2. Heuristic Method 16
3.2.1. Notation 16
3.2.2. Heuristic Algorithm 18
4. Computational Experiments and Result 20
4.1. Experiment Design 20
4.2. Comparisons 23
5. Conclusion 27
Appendix A 29
Appendix B 35
References 49

References
Dyer, M. E., and Wolsey, L. A. (1990), “Formulating the single machine sequencing problem with release dates as a mixed integer program”, Mathematics, Vol. 26, No. 2-3, pp.255-270.
Degraeve, Z., and Vandebroek, M. (1998), “A mixed integer programming model for solving a layout problem in the fashion industry”, Management Science, Vol. 44, No. 3, pp. 301-310.
Degraeve, Z., Gochet, W., and Jans, R. (2002), “Alternative formulations for a layout problem in the fashion industry”, European Journal of Operational Research, Vol. 143, No. 1, pp. 80-93.
Jacobs-Blecha, C., Ammons, J. C., Schutte, A., and Smith, T. (1998), “Cut order planning for apparel manufacturing”, IIE Transactions, Vol. 30, No. 1, pp. 79-90.
Johnston, R. E., and Sadinlija, E. (2004), “A new model for complete solutions to one-dimensional cutting stock problems”, European Journal of Operational Research, Vol. 153, No. 1, pp. 176–183.
Keha, A. B., Khowala, K., and Fowler, J. W. (2009), “ Mixed integer programming formulations for single machine scheduling problems”, Computers and Industrial Engineering, Vol. 56, No. 1, pp. 357-367.
Martens, J. (2004), “Two genetic algorithms to solve a layout problem in the fashion industry”, European Journal of Operational Research, Vol. 154, No. 1, pp. 304-322.
Rose, D. M., and Shier, D. R. (2007), “Cutting scheduling in the apparel industry” Computers and Operations Research, Vol. 34, No.11, pp. 3209-3228.
Reinertsen, H., and Vossen, T. W. M. (2010), “The one-dimensional cutting stock problem with due dates”, European Journal of Operational Research, Vol. 201, No. 3, pp. 701-711.
Wong, W.K., and Leung, S.Y.S. (2008), “Genetic optimization of fabric utilization in apparel manufacturing”, International Journal of Production Economics, Vol. 114, No. 1, pp. 376-387.
Yuen, B. J., and Richardson K. V. (1995), “Establishing the optimality of sequencing heuristics for cutting stock problems”, European Journal of Operational Research, Vol. 84, No. 3, pp. 590-598.
Yuen, B. J. (1995), “Improved heuristics for sequencing cutting patterns”, European Journal of Operational Research, Vol. 87, No. 1, pp. 57-64.
Yanasse, H. H., and Lamosa, M. J. P. (2007), “An integrated cutting stock and sequencing problem”, European Journal of Operational Research, Vol. 183, No. 3, pp. 1353-1370.