关键词: 双代理排序, 序列分批, 计算复杂性, 时间表长, 总完工时间

Abstract: 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.

Key words: two-agent scheduling, serial-batching, computational complexity, makespan, total completion time