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.

生产全球化推动了合同制造（Contract Manufacturing, CM）模式的应用，有效提升了生产资源的高效利用效率。在此模式中，多家以代理方身份存在的原始品牌制造商，会将自身生产任务委托给单一原始设备制造商（Original Equipment Manufacturer, OEM）。在此场景下，各代理方共享生产资源的同时，还会彼此竞争资源的使用优先级。为揭示这类竞争性代理方的运作本质，本文针对双代理单处理器调度问题展开研究。该研究引入释放时间（release date），以贴合实际生产场景中订单陆续到达的情形。本文的研究目标为最小化双代理的最大延误总和，进而提升客户满意度。针对这一NP难问题，本文构建了混合整数规划模型。针对小规模问题，本文提出了一种具备有效下界与分支策略的分支定界算法，并辅以基于修正最早交货期列表的启发式算法以提供初始上界。针对中等规模问题，本文开发了一种混合离散差分进化算法，该算法融合了改进的交叉、变异操作与可变邻域搜索策略，以规避局部最优解。仿真实验验证了所提算法的高效性。