Welcome to i4QLRT

Make / Assembly Line Balancing Problem / Heuristics / Rank Positional Weight Method

This is the python code of the Rank Positional Weight 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 Rank positional weight method (RPWM) was proposed by Helgeson and Birnie in 1961.The position weight of each task is obtained by adding up all subsequent task times, including itself. The point to be considered here is that the task with a high position weight is selected in the first assignment process. The steps applied in the rank positional weight method technique are as follows:

• Step 1: A priority relationship diagram is drawn.
• Step 2: Position weight (position weight) is calculated for each task. The position weight of a task is the sum of the time required to perform that task and the duration of the tasks that follow that task.
• Step 3: Tasks are sorted by position weight from largest to smallest.
• Step 4: The task with the highest position weight is selected and assigned to the workstation.
• Step 5: After the task with the highest position weight is assigned to the workstation, the task with the highest position weight is selected among the remaining tasks and assigned to the station considering the following constraints. a) The reserved jobs list is checked. If tasks with no predecessor are assigned, go to b; if not, go to step 6. b) The durations of the tasks are compared to the unused time of the station. If the duration of the task to be assigned is less than the unused time, the assignment is made and the unused time of the station is re­calculated and step 5 is repeated, if it is greater than the unused time, step 6 is passed.
• Step 6: The process continues until the assignment to the station is selected, checked, and, if possible, until two conditions are met: a) All work items are assigned. b) There are no tasks that meet the priority requirement and the unassigned time requirement.
• Step 7: The task with the highest position weight that is not assigned is assigned to the next station, and the first six steps are repeated.
• Step 8: Assignment continues until all tasks are assigned to the workstations. After the implementation of all these steps, the assembly line balancing problem is solved.