Meta-heuristic algorithms for parallel identical machines scheduling problem with weighted late work criterion and...

Area of Science:

• Operations Research
• Computer Science
• Optimization

Background:

• The parallel machines scheduling problem with weighted late work and common due date is a complex, NP-hard problem.
• Evaluating scheduling quality requires considering the weighted late work criterion, focusing on job lateness.
• Existing scheduling algorithms like List Scheduling (LS) and Longest Processing Time (LPT) provide baseline performance.

Purpose of the Study:

• To investigate the application of meta-heuristic algorithms for the parallel machines scheduling problem with weighted late work.
• To introduce and evaluate a novel Largest Density First (LDF) algorithm, an improvement over Longest Processing Time (LPT).
• To compare the performance of Ant Colony System (ACS), Genetic Algorithm (GA), Simulated Annealing (SA), LDF, LPT, and LS.

Main Methods:

• Implementation of three meta-heuristic algorithms: Ant Colony System (ACS), Genetic Algorithm (GA), and Simulated Annealing (SA).
• Development of a new algorithm, Largest Density First (LDF), derived from the Longest Processing Time (LPT) heuristic.
• Computational experiments comparing the performance of ACS, GA, SA, LDF, LPT, and LS on the parallel machines scheduling problem.

Main Results:

• Simulated Annealing (SA) demonstrated superior performance across most experimental scenarios.
• The novel Largest Density First (LDF) algorithm achieved competitive results, outperforming SA in specific conditions.
• LDF exhibited significantly shorter computation times compared to SA, indicating greater efficiency.

Conclusions:

• Meta-heuristic algorithms, particularly SA, are effective for solving the NP-hard parallel machines scheduling problem with weighted late work.
• The proposed LDF algorithm offers a promising alternative, balancing performance with computational efficiency.
• Further research can explore hybrid approaches combining meta-heuristics with LDF for enhanced scheduling solutions.