订单可拆开加工的两代理分批调度问题  

Two-Agent Parallel-Batch Scheduling with Split Orders

作　　者：刘甲玉[1] 耿志超 LIU Jiayu;GENG Zhichao(Department of Public Basic Education, Henan College of Transportation, Zhengzhou 450001, China;School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China)

机构地区：[1]河南交通职业技术学院公共基础教学部,郑州450001 [2]郑州大学数学与统计学院,郑州450001

出　　处：《西南师范大学学报（自然科学版）》2022年第1期21-27,共7页Journal of Southwest China Normal University(Natural Science Edition)

基　　金：国家自然科学基金项目(11771406).

摘　　要：研究平行批机器环境下两代理调度问题.其中,来自两个代理的订单竞争使用同一机器资源,所有订单均可拆分并在相邻的批中加工,目标是寻找一个调度方案,使得在保证其中一个代理的所有订单的最大加工费用不超过预算的条件下,最小化另一个代理的所有订单的平均完工时间.本文证明了此问题是NP难的,并对它的一种特殊情形给出了一个基于动态规划的多项式时间算法.In this paper,the scheduling problem has been investigated on a single parallel-batch machine where orders belong to two competing agents and are of equal length but different size.Each order's size can be arbitrarily split into two parts and processed in the consecutive batches.It is not permitted to process the orders from different agents in a common batch.It is shown that it is NP-hard for the problem of minimizing the total completion time of the jobs of one agent,subject to the maximum cost of the jobs of the other agent being upper bounded by a threshold,and also provides a dynamic program algorithm for its one special case.

关 键 词：调度 平行批 两代理 可拆分订单 

分 类 号：O224[理学—运筹学与控制论]