Project Management and Scheduling 2022
Project Management and Scheduling (PMS) is an international workshop dedicated to Project Management and Scheduling. The workshop provides an ideal opportunity to discuss recent and important issues in the field of project management (planning, scheduling, control) and machine scheduling (single and parallel machine problems, flow shop, job shop).
We congratulate our colleague Léa Blaise, Optimization Scientist at LocalSolver, for being nominated for the Best Student Paper Award at the 18th International Workshop on Project Management and Scheduling (PMS 2022) for her paper on Solving the Assembly Line Balancing Problem with LocalSolver.
The Assembly Line Balancing Problem is described as follows. We consider a set of tasks, of fixed duration, that are partially ordered by precedence relations. The problem consists in assigning the tasks to workstations while ensuring that the total duration of a workstation’s tasks does not exceed the cycle time. The precedence relations between the tasks impose that a task can be assigned to the same workstation as its predecessors, or to a later workstation, but cannot be assigned to an earlier workstation. The objective is to minimize the number of workstations used.
In her paper, Léa considers a family of problems presenting a packing structure, such as the Bin Packing Problem, and an ordering structure, such as the Assembly Line Balancing Problem. She introduces a greedy algorithm, making use of both kinds of structures to build feasible solutions. She shows how it can be used both as an initialization algorithm and as a “destroy and repair” local move. She also introduces a packing move based on ejection chains, particularly efficient on the most combinatorial packing instances. Their integration into LocalSolver enables it to obtain great results on the targeted problems.
Léa will do her presentation online at the Student Award 2 session at PMS 2022 on the 7th of April at 9:00 am. If you would like to learn more about modeling and solving Assembly Line Balancing problems with LocalSolver, please attend her talk at this link.
To get figures about how LocalSolver performs on the Simple Assembly Line Balancing Problem (SALBP), you can check this benchmark against Gurobi 9.1 and IBM CPLEX CP Optimizer 20.1.0.
Don’t hesitate to contact us; we will be glad to exchange about your optimization problems.