Robust Scheduling of Two-Agent Customer Orders with Scenario-Dependent Component Processing Times and Release Dates

Although some uncertainty factors can occur in many practical environments, customer order scheduling problems involving two agents in such uncertain environments have not received attention in the current literature. Motivated by this observation, we address a two-agent customer order scheduling problem where various customer orders have scenario-dependent component processing times and release dates in order to find an appropriate schedule to minimize the maximum of the total completion time of the customer orders that belong to one agent and are subject to a constraint with the other agent. In order to solve this problem, a lower bound and six dominant properties are derived and used to propose a branch-and-bound algorithm to find an exact optimal solution. Afterward, three local search heuristics and two variants of a simulated annealing hyper-heuristic are proposed and empirically evaluated in order to find approximate solutions. Finally, we conclude the paper with a summary of our findings and some directions for future research.

Automated summary

This paper addresses the customer order scheduling problem involving two agents in uncertain environments. It proposes a branch-and-bound algorithm and several heuristics to find optimal or approximate solutions. The empirical evaluation demonstrates the effectiveness of the proposed methods in finding good solutions.