Welcome to i4QLRT

Make / Assembly Line Balancing Problem / Heuristics / Kilbridge and Wester algorithma

This is the python code of the Kilbridge and Wester algorithm to solve the Assembly Line Balancing Problem.

Problem description

The Assembly Line Balancing Problem (ALBP) is a production planning problem that seeks to optimize the assignment of tasks to workstations on an assembly line to meet a required production rate while minimizing costs. In the ALBP, a set of tasks must be assigned to a set of workstations along a production line, with each task having a predetermined processing time and each workstation having a maximum capacity, defined by the maximum cycle time. The objective is to minimize the number of workstations required and to minimize the total idle time of the workstations. A given number of T tasks should be executed in W workstations. Tasks can have predecessors, therefore a task can be assigned to a workstation only if all the predecessors have been assigned to previous workstations or to such workstation. The problem is to determine the optimal such arrangement, i.e. the one with the shortest possible total job execution makespan. The number of possible solutions in the ALBP is equal to W multiplied by itself T-1 times, or W^(T-1). For example, if there are 5 workstations and 60 tasks, the total number of possible solutions in the ALBP is 5^59 = 173,472,347,597,680,709,441,192,448,139,190,673,828,125. The ALBP is a combinatorial optimization problem and can be solved using various heuristic and exact algorithms.

Algorithm description

The Kilbridge and Wester heuristic was first used in 1961. It is used in studies in the literature because it successfully solves assembly line balancing problems that are difficult to solve. In this method, among the heuristic methods, work items are assigned to workstations according to their positions in the priority diagram. The implementation steps of Kilbridge and Wester Heuristics are as follows:

• Step 1: A priority relationship diagram is drawn.
• Step 2: Tasks without predecessors are listed in the first column. When the second column is passed, the tasks followed by the tasks in the first column are listed. This process is continued until all columns are created.
• Step 3: The durations of the tasks in each column are summed, and the cumulative duration is obtained.
• Step 4: The cycle time is determined.
• Step 5: Tasks are assigned to the station in a way that does not exceed the cycle time. If tasks exceed the cycle time when assigned to the station, that task is assigned to the next station.
• Step 6: The cumulative duration of unassigned tasks is recalculated, and step 5 is repeated.
• Step 7: Assignment processes continue until all tasks are assigned to the workstations.