Proposed a branch and bound algorithm for Assembly flow shop scheduling problem

Abstract

Assembly flow shop production system includes two stages. In the first stage that is usually assumed one station with some parallel machines, the parts are processed. The second stage is an assembly station (or line) to assemble the parts and complete the products. Suppose that a number of products of different kinds are ordered to be produced and each product needs a set of several parts to complete. Some of the parts are common and some others are unique for each product. Therefore it is important to study the setup times and batch production. The aim is to schedule the parts for process and the products for assembly with the minimum complete time objective. Literature review shows that the considered problem is a NP-Hard problem, so the problem characteristics and its parameters are defined and then a branch and bound algorithm is introduced to solve the small and mediocre problems. Some lower bounds and upper bounds are improved to increase the algorithm efficiency. Finally, a variety of problem is designed and performance of the proposed algorithm is evaluated in solving this problems.

Keywords

• scheduling
• assembly flow shop. branch &
• amp
• bound algorithm
• makespan