同时最优化时间表长与总完工时间的双代理单机序列分批排序问题

Two-agent Scheduling to Minimize Makespan and Total Completion Time on a Serial-batching Machine

本文研究在一台序列分批处理机上同时最优化A代理的时间表长和B代理的总完工时间的双代理排序问题.在序列分批的背景下,工件被分批加工(但不同代理的工件不能在同一批中加工,且每个代理都希望最小化仅依赖于各自工件完工时间的费用函数)且一批的加工时间等于这一批中所有工件的加工时间和.而且在一个新批开始加工前,机器有一个常数的安装时间.此外,根据批容量,序列分批模型又被分成有界模型和无界模型.在本文中,我们对所研究问题的有界模型和无界模型分别给出了一个多项式时间算法.

This paper studies the two-agent scheduling on a serial-batching machine to minimize the makespan of agent A and the total completion time of agent B simultaneously.Under the serial-batching setting,the jobs are processed in batches and the processing time of a batch is equal to the sum of processing times of jobs in the batch,but jobs of different agents cannot be processed in a common batch and the cost function of an agent depends on its jobs only.Moreover,when a new batch starts,a constant setup time is required for the machine.According to the capacity of a batch,the serial-batching model is divided into the unbounded model and the bounded model.In the paper,we present a polynomial-time algorithm for the bounded model and the unbounded model,respectively.