题名

A CPM-Based Bidirectional Approach for Type-Ⅰ Assembly Line Balancing Problem

并列篇名

第一類型組裝線平衡問題之雙向要徑啟發式演算法

DOI

10.29977/JCIIE.200811.0005

作者

葉丁鴻(Din-Horng Yeh)；高秀學(Hsiu-Hsueh Kao)

关键词

組裝線平衡問題 ； 啟發式演算法 ； 要徑法 ； 雙向式演算法 ； assembly line balancing problem ； heuristic ； critical path method ； bidirectional

期刊名称

工業工程學刊

卷期/出版年月

25卷6期（2008 / 11 / 01）

页次

481 - 487

内容语文

繁體中文
中文摘要

第一類型組裝線平衡問題(ALBP-Ⅰ)，其目的是在已知產出時間的條件下，求解以最少工作站來平衡組裝線的工作。ALBP-Ⅰ是作業管理領域中著名的難解問題之一。過去數十年來，雖然學者們針對此問題發展出許多具有最佳解的演算法（例如0-1整數規劃模式、分枝限定演算法、動態規劃模式等），然而其共同缺點爲在求解大型問題時，計算缺乏效率性。基於實務上的需求，本研究提出一個有效的啟發式演算法，此演算法係結合專案管理的要徑法和雙向式的演算法。從本研究在文獻問題的測試結果，可以看出此演算法的效率(efficiency)與有效性(effectiveness)。
英文摘要

In this paper we consider the so-called type-Ⅰ assembly line balancing problem (ALBP-I), in which the objective is to minimize the number of workstations needed for a given cycle time. ALBP-Ⅰ is one of the well-known NP-hard problems in operations management, and many optimal approaches (including 0-1 integer programming model, branch and bound algorithm, dynamic programming model, etc.) have been developed during the past decades. However, all optimal approaches share the disadvantage of being computationally inefficient in solving large-scale problems, and which makes heuristics a necessity in practice. We propose in this paper a new approach, based on the recently proposed bidirectional heuristic and the critical path method (CPM) of project management, to resolve the issue of task assignment for ALBP-Ⅰ. A numerical example is given for illustration, and several sample problems are solved to show the effectiveness of the proposed approach.
主题分类 工程學 > 工程學總論
参考文献
  1. Bryton, B.(1954).M.S. Thesis, Northwestern University.Evanston, IL:Northwestern University.
  2. Carraway, R. L.(1989).A dynamic programming approach to stochastic assembly line balancing.Management Science,35,459-471.
  3. Ghosh, S.,R. J. Gagnon(1989).A comprehensive literature review and analysis of the design balancing and scheduling of assembly systems.International Journal of Production Research,27,637-670.
  4. Graves, S.C.,B.W. Lamar(1983).An integer programming procedure for assembly system design problems.Operations Research,31,522-545.
  5. Gutjahr, A. L.,G. L. Nemhauser(1964).An algorithm for the line balancing problem.Management Science,11,308-315.
  6. Heskiaoff, H.(1968).A heuristic method for balancing assembly lines.The Western Electric Engineer,12,9-13.
  7. Kao, H. H.,D. H. Yeh(2006).A new approach for assembly line balancing problems.Proceeding of The 36th International Conference on Computers and Industrial Engineering,Taipei, Taiwan:
  8. Salveson, M. E.(1955).The assembly line balancing problem.The Journal of Industrial Engineering,6,18-25.
  9. Scholl, A.(1999).Balancing and Sequencing of Assembly Lines.New York:Physica-Verlag Heidelberg.
  10. Scholl, A.,R. Klein(1997).SALOME: a bidirectional branch and bound procedure for assembly line balancing.INFORMS Journal on Computing,9,319-334.
  11. Scholl, A.,S. Voß(1996).Simple assembly line balancing-heuristic approaches.Journal of Heuristics,2,217-244.
print cancel