A Petri net approach for simple assembly line balancing problems

摘要

A simple assembly line balancing problem of type-1 (SALBP-1) aims to minimize the number of workstations for a given cycle time. In the relevant literature, several heuristics based on a branch-and-bound procedure, tabu search, and genetic algorithms (GAs) were proposed to solve SALBP-1. In this paper, an algorithm based on the reachability analysis of Petri nets is developed for SALBP-1. The proposed algorithm searches enabled transitions (or assignable tasks) in the Petri net model of precedence relations between tasks, and then the task minimizing the idle time is assigned to the station under consideration. 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 optimal solutions of traditional heuristics and a GA.