A bi-agent single-processor scheduling to minimize the sum of maximum lateness with release dates

The globalization of production promotes the adoption of Contract Manufacturing (CM) mode, enhancing the efficient utilization of production resources. In this mode, multiple Original Brand Manufacturers, acting as agents, delegate their production tasks to a single Original Equipment Manufacturer. In this scenario, agents share production resources and compete priority for each other. To reveal the nature of the competitive agents, this article investigates a bi-agent single-processor scheduling problem. It incorporates release dates to reflect the scenario where orders arrive in actual production settings. The objective is to enhance customer satisfaction by minimizing the sum of maximum lateness of two agents. A mixed integer programming model is formulated to address this NP-hard problem. For small-scale problems, a branch and bound algorithm featuring effective lower bound and branching strategy is proposed. It is complemented by a heuristic algorithm based on Earliest Due Date List-Revising, providing an initial upper bound. For middle-scale problems, a hybrid discrete differential evolution algorithm is developed, incorporating enhanced crossover and mutation operations and a variable neighborhood search strategy to avoid local optima. Simulation experiments endorse the high efficiency of the proposed algorithms.