Iterated Local Search and Other Algorithms for Buffered Two-Machine Permutation Flow Shops with Constant Processing...

Area of Science:

• Operations Research
• Industrial Engineering
• Computer Science

Background:

• The two-machine permutation flow shop scheduling problem with buffers is relevant in manufacturing and logistics.
• This problem is often NP-hard, posing significant computational challenges for finding optimal solutions.

Purpose of the Study:

• To analyze the complexity of the two-machine flow shop problem with buffers under a specific condition of constant processing times.
• To develop efficient algorithms and heuristics for solving this NP-hard scheduling problem.

Main Methods:

• Investigated the NP-hard nature of the problem, even with constant processing times.
• Developed a polynomial-time algorithm (2BF-OPT) for a specific solvable case (c > p_j or c < p_j).
• Proposed two heuristics: a modified NEH (mNEH) and an Iterated Local Search (2BF-ILS) utilizing mNEH.

Main Results:

• Confirmed the NP-hard status for most buffer flow shop problems with constant processing times.
• Demonstrated that 2BF-OPT solves the special case in O(nlogn) time.
• 2BF-ILS outperformed existing state-of-the-art algorithms and Ant Colony Optimization for buffered flow shop problems.

Conclusions:

• The study provides both exact and heuristic solutions for buffered flow shop scheduling problems.
• The 2BF-ILS heuristic offers a competitive and efficient approach for NP-hard instances.
• The research contributes to optimizing scheduling in scenarios with constant processing times on one machine.