A P-invariant-based algorithm for simple assembly line balancing problem of type-1

作者：Kilincci Ozcan^*; Bayhan G Mirac

来源：International Journal of Advanced Manufacturing Technology, 2008, 37(3-4): 400-409.

DOI：10.1007/s00170-007-0975-2

• assembly line balancing
• Petri nets
• SALBP-1
• heuristics

A simple assembly line balancing problem of type-1 (SALBP-1) concerns minimizing the number of workstations on an assembly line for a given cycle time. In this problem only a single product with deterministic task times is considered. Since the SALBP-1 is known as an NP-hard, considerable research effort has been spent to develop heuristic approaches. In this study we develop a different heuristic approach based on the P-invariants of Petri nets. The algorithm is coded in MATLAB, and its efficiency is tested on Talbot's and Hoffmann's benchmark datasets according to some performance measures and classifications. A computational study validates its effectiveness on Tonge's 70-task problem by comparison with solutions of traditional heuristics and a genetic algorithm reported to perform well.

• 出版日期2008-5