A Petri net approach for simple assembly line balancing problems

KILINÇCI Ö., Bayhan G. M.

INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, cilt.30, ss.1165-1173, 2006 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 30
  • Basım Tarihi: 2006
  • Doi Numarası: 10.1007/s00170-005-0154-2
  • Dergi Adı: INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.1165-1173
  • Anahtar Kelimeler: assembly line balancing, Petri nets, reachability analysis, SALBP-1, heuristics, AUTOMATED MANUFACTURING SYSTEMS, GENETIC ALGORITHMS, DESIGN, OPERATION, MODELS
  • Dokuz Eylül Üniversitesi Adresli: Evet

Özet

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.