Welcome to i4QLRT

Make / Assembly Line Balancing Problem / Heuristics / Computer Method of Sequencing Operations for Assembly Lines algorithm

This is the python code of the Computer Method of Sequencing Operations for Assembly Lines (COMSOAL) 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 COMSOAL algorithm was developed by Albert Leon Guiffrida and published in 1969. The main objective of COMSOAL is to minimize the total time required to complete a set of tasks or operations in an assembly line, taking into account various constraints and factors such as precedence relationships between operations, task durations, and workstations' capacities. By optimizing the sequencing of operations, COMSOAL aims to improve the efficiency and productivity of assembly lines. The implementation steps of COMSOAL algorithm are as follows:

• Step 1: A priority relationship diagram is drawn.
• Step 2: Tasks without predecessors are listed. The list is randomly shuffled.
• Step 3: The fist task on the list is selected.
• Step 4: Such task is assigned to the current workstation if this addition does not exceed the cycle time. If tasks exceed the cycle time when assigned to the station, the next task in the list is selected (back to Step 3). If all tasks in the list have been tested for insertion into the workstation and none could be inserted, return to Step 2.
• Step 5: Assignment processes continue until all tasks are assigned to the workstations.

These steps generate one of the possible solutions. The algorithm can be repeated in a loop, so that the best solution is recorded. The result is the best solution obtained after a maximum number of loops or computing time. Many alternative solutions can be provided with this method.