1668. Heuristics for solving Reentrant Permutation Flow Shop Problems
Invited abstract in session WA-20: Topics in Combinatorial Optimization 3, stream Combinatorial Optimization.
Wednesday, 8:30-10:00Room: Esther Simpson 2.11
Authors (first author is the speaker)
| 1. | Itamar Segal
|
| Industrial Engineering and Management, Ariel University | |
| 2. | Tal Grinshpoun
|
| Industrial Engineering and Management and Ariel Cyber Innovation Center, Ariel University | |
| 3. | Elad Shufan
|
| physics, SCE, Sami Shamoon College of Engineering | |
| 4. | HAGAI ILANI
|
| Industrial Eng. and management, Shamoon College of Engineering |
Abstract
In a permutation flow shop (PFS), jobs are serially processed on a set of machines, with the same machine order for all jobs (flow shop) and the same job order on each machine (permutation). While the meaning of "permutation" is clear for flow shop, it is ambiguous for a reentrant flow shop (RFS). In RFS, jobs may revisit some machines, leading to multiple interpretations of permutation; different researchers have interpreted the term under varying assumptions. To clarify this inconsistency, we defined four permutation types for a reentrant permutation flow shop (RPFS) with a cyclic pattern.
Building on this foundation, we investigate the impact of the four types on both optimization and heuristic performance, focusing on the makespan objective. We first show that the best possible solution can be achieved under each of the four types. We then conduct a statistical evaluation of solution quality on small-scale problem instances.
In addition, we extend several well-known PFS heuristics, including NEH, to all four permutation definitions. We conduct computational experiments to evaluate the effectiveness of these heuristics. A direct extension of known heuristics to RPFS results in poor solutions for two permutation types that allow level passing. We propose methods to address this, such as restricting level passing. Beyond their immediate significance, these findings provide insights for developing metaheuristics specifically designed for RPFS problems.
Keywords
- Scheduling
- Manufacturing
Status: accepted
Back to the list of papers