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

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.