Symbiotic organisms search algorithm for the unrelated parallel machines scheduling with sequence-dependent setup...

Area of Science:

• Operations Research
• Computer Science
• Optimization

Background:

• Addresses makespan minimization on unrelated parallel machines with sequence-dependent setup times.
• Symbiotic Organisms Search (SOS) is a popular global optimization technique adapted for discrete optimization.
• Existing methods may not optimally handle the complexities of unrelated parallel machine scheduling.

Purpose of the Study:

• To develop an improved Symbiotic Organisms Search (SOS) algorithm for the unrelated parallel machine scheduling problem (UPMSP).
• To enhance the solution quality and performance of the SOS algorithm for this specific scheduling challenge.
• To evaluate the effectiveness of the proposed algorithms against existing techniques.

Main Methods:

• Developed a new solution representation and decoding procedure for the SOS algorithm to suit UPMSP.
• Incorporated an iterated local search strategy with insertion and swap moves to improve solution quality.
• Designed a machine assignment heuristic using the Longest Processing Time first (LPT) rule for dynamic load balancing.

Main Results:

• The proposed SOS with LPT (SOS-LPT) heuristic achieved the best performance among tested methods.
• The enhanced SOS algorithm closely followed SOS-LPT in performance, indicating effectiveness.
• Statistical tests confirmed significant performance variations, favoring the proposed approaches.

Conclusions:

• The SOS-LPT heuristic and the enhanced SOS algorithm are effective and reasonable solutions for large-scale UPMSPs.
• The novel adaptations make the SOS algorithm suitable for complex scheduling problems.
• The study validates the performance improvements achieved through the integrated heuristic and local search strategies.