Simple assembly line balancing problem: A petri net approach

Much research has been devoted to the simple assembly line balancing problem-type 1 (SALBP-1). The objective is to minimize number of stations for a given cycle time. As they are known as NP-hard problems, approximate or heuristic approaches are extremely required for solving these problems. In this thesis, heuristic algorithms based on Petri nets (PNs) are proposed to solve SALBP-1. Although PNs have been widely used as mathematical and graphical tools in the area of assembly systems, a great deal of research attention has been rather focused on modeling, controlling, planning, task sequencing, and scheduling. The thesis involves particularly a review of the recent research works that applied to SALBP-1, and a review of PNs applications on manufacturing systems. In these works, classification frameworks are provided. Complexity analyses of the proposed algorithms are presented. A problem is considered to demonstrate the application of these algorithms. All iterations of solutions are given in details. The algorithms are coded in MATLAB, the language of technical computing, and are compared with each other and with existing algorithms on the sets of large test problems from the literature. Keywords: Assembly line balancing, Petri nets, Manufacturing systems, Reachability analysis, T-invariants, P-invariants, SALBP-1.