本論文考量兩階段組裝排程且包含設置時間之問題，目標為最大完工時間最小化。在第一階段，製造機器生產各種元件；而當元件的數量滿足組裝需求時，第二階段的組裝機器把元件組裝成產品。我們將問題建構為一個數學模型且找到了一些最佳解性質。接著，我們利用這些最佳解性質的概念，提出一個啟發法求解此問題，並以下限值評估啟發法之績效。實驗結果證明，此啟發法可在極短的時間內得到近似最佳解，其平均誤差為0.478%。

This thesis considers a two-stage assembly scheduling of products problem with setup time to minimize the makespan. In this problem, there is a machining machine in the first stage which produces components. When the required components are available, a single assembly machine in the second stage assembles these components into products. We formulate the problem as a mixed integer programming model and find several properties for the optimal solutions. Moreover, an efficient heuristic based on these optimal properties is proposed. A lower bound is also derived for evaluating the performance of the proposed heuristic. Computational results show that the heuristic can obtain a near optimal solution in almost zero time and the average percentage deviation is only 0.478.

Allahverdi, A., Al-Anzi, F. S. 2006. Evolutionary heuristics and an algorithm for the two-stage assembly scheduling problem to minimize makespan with setup times. International Journal of Production Research, 44, 4713-4735.
Al-Anzi, F. S., Allahverdi, A. 2007. A self-adaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times. European Journal of Operational Research, 182, 80-94.
Al-Anzi, F. S., Allahverdi, A. 2009. Heuristics for a two-stage assembly flowshop with bicriteria of maximum lateness and makespan. Computers & Operations Research, 36, 2682–2689.
Cheng, T. C. E., Wang, G. 1999. Scheduling the fabrication and assembly of components in a two-machine flowshop. IIE Transactions, 31, 135-143.
Demoly, F., Yan, X. T., Eynard, B., Rivest, L., Gomes, S. 2011. An assembly oriented design framework for product structure engineering and assembly sequence planning. Robotics and Computer Integrated Manufacturing, 27, 33-46.
Guo, Z. X., Wong, W. K. 2008. A genetic-algorithm-based optimization model for scheduling flexible assembly lines. International Journal of Advanced Manufacturing Technology, 36, 156-168.
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.
Hatami, S., Ebrahimnejad, S., Tavakkoli-Moghaddam, R., Maboudian, Y. 2010. Two meta-heuristics for three-stage assembly flowshop scheduling with sequence-dependent setup times. International Journal of Advanced Manufacturing Technology, 50, 1153-1164.
He, D., Babayan, A., Kusiak, A. 2001. Scheduling manufacturing systems in an agile environment. Robotics and Computer Integrated Manufacturing, 17, 87-97.
He, D., Babayan, A. 2002. Scheduling manufacturing systems for delayed product differentiation in agile manufacturing. International Journal of Production Research, 40, 2461-2481.
Johnson, S. M. 1954. Optimal two-and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1, 61-68.
Kusiak, A. 1989. Aggregate scheduling of a flexible machining and assembly system. IEEE Transactions on Robotics and Automation, 5, 451-459.
Lee, C. Y., Cheng, T. C. E., Lin, B. M. T. 1993. Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem. Management Science, 39, 616-625.
Lee, D. H., Cao, Z., Meng, Q. 2007. Scheduling of two-transtainer systems for loading outbound containers in port container terminals with simulated annealing algorithm. International Journal of Production Economics, 107, 115-124.
Lin, B. M. T., Cheng, T. C. E. 2002. Fabrication and assembly scheduling in a two-machine flowshop. IIE Transactions, 34, 1015-1020.
Lin, S. W., Ying, K. C., Lee, Z. J. 2009. Metaheuristics for scheduling a non-permutation flowline manufacturing cell with sequence dependent family setup times. Computers & Operations Research, 36, 1110–1121.
Liao, C. J., Liao, C. C. 2007. An ant colony optimization algorithm for scheduling in agile manufacturing. International Journal of Production Research, 46, 1813-1824.
Liao, C. J., Chen, P. T. 2008. Manufacture and assembly scheduling with batch setup times in a two-machine flowshop. Unpublished master’s thesis, National Taiwan University of Science and Technology, Taiwan.
Manjeshwar, P. K., Damodaran, P., Srihari, K. 2009. Minimizing makespan in a flow shop with two batch-processing machines using simulated annealing. Robotics and Computer Integrated Manufacturing, 25, 667-679.
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, 346-355.
Raj, M. V., Sankar, S. S., Ponnambalam, S. G. 2012. Particle swarm optimization algorithm to maximize assembly efficiency. International Journal of Advanced Manufacturing Technology, 59, 719-736.
Rashid, M. F. F., Hutabarat, W., Ashutosh, T. 2012. A review on assembly sequence planning and assembly line balancing optimization using soft computing approaches. International Journal of Advanced Manufacturing Technology, 59, 335-349.
Sung, C. S., Kim, H. A. 2009. A two-stage multiple-machine assembly scheduling problem for minimizing sum of completion times. International Journal of Production Economics, 113, 1038-1048.
Tian, Y., Liu, D., Yuan, D., Wang, K. 2013. A discrete PSO for two-stage assembly scheduling problem. International Journal of Advanced Manufacturing Technology, 66, 481-499.
Torabzadeh, E., Zandieh, M. 2010. Cloud theory-based simulated annealing approach for scheduling in the two-stage assembly flowshop. Advance in Engineering Software, 41, 1238-1243.
Tseng, Y. J., Yu, F. Y., Huang, F. Y. 2010. A multi-plant assembly sequence planning model with integrated assembly sequence planning and plant assignment using GA. International Journal of Advanced Manufacturing Technology, 48, 333-345.
Tseng, Y. J., Yu, F. Y., Huang, F. Y. 2011. A green assembly sequence planning model with a closed-loop assembly and disassembly sequence planning using a particle swarm optimization method. International Journal of Advanced Manufacturing Technology, 57, 1183-1197.
Yokoyama, M. 2004. Scheduling for two-stage production system with setup and assembly operations. Computers & Operations Research, 31, 2063–2078.
Yokoyama, M. 2008. Flow-shop scheduling with setup and assembly operations. European Journal of Operational Research, 187, 1184-1195.
Zhou, W., Zheng, J. R., Yan, J. J., Wang, J. F. 2011. A novel hybrid algorithm for assembly sequence planning combining bacterial chemotaxis with genetic algorithm. International Journal of Advanced Manufacturing Technology, 52, 715-724.