Single-machine scheduling to minimize total completion time and tardiness with two competing agents

Area of Science:

• Operations Research
• Scheduling Theory
• Computational Intelligence

Background:

• Single-machine scheduling problems are fundamental in operations research.
• Multi-agent scheduling introduces complexities in resource allocation and objective optimization.
• Balancing competing objectives like completion time and tardiness is a common challenge.

Purpose of the Study:

• To develop an optimal scheduling algorithm for a two-agent single-machine environment.
• To minimize a weighted combination of total completion time and total tardiness for the first agent.
• To ensure zero tardiness for the second agent's jobs.

Main Methods:

• A branch-and-bound algorithm was developed to find the optimal job sequence.
• Two simulated annealing heuristic algorithms were proposed for near-optimal solutions.
• Computational experiments were conducted to evaluate algorithm performance.

Main Results:

• The branch-and-bound algorithm successfully identified optimal job sequences.
• Simulated annealing algorithms provided effective near-optimal solutions.
• Performance evaluation demonstrated the efficacy of the proposed methods.

Conclusions:

• The developed algorithms are effective for solving the considered single-machine two-agent scheduling problem.
• The study contributes efficient methods for optimizing complex scheduling objectives.
• Further research can explore extensions to more agents or machine environments.