A further study on two-agent scheduling on an unbounded serial-batch machine with batch delivery cost. (September 2017) - Qi, Xianglai; Yuan, Jinjiang
Highlights: Unbounded serial-batch machine. Two-agent scheduling with batch delivery cost. Total completion time and maximum lateness. Polynomial-time Algorithms. Abstract: For the two-agent scheduling on an unbounded serial-batch machine with batch delivery cost, Yin et al. (2016) presented a comprehensive study, where the objective of each agent ( A or B ) is calculated by his scheduling cost plus his batch delivery cost proportional to the number of batches of this agent. Among their results, they provided a polynomial-time algorithm for minimizing the objective of agent A subject to the constraint that the objective of agent B does not exceed a given threshold value, where the criterion of agent A is the total completion time plus batch delivery cost and the criterion of agent B is the maximum lateness plus batch delivery cost. We show in this paper that their algorithm is incorrect by a counterexample and the algorithm presented in Kovalyov et al. (2015) for solving the same problem without batch delivery cost can be used to solve the problem in Yin et al. (2016) in polynomial time. We further study two corresponding Pareto scheduling problems and provide polynomial-time algorithms.