A further study on two-agent parallel-batch scheduling with release dates and deteriorating jobs to minimize the makespan

Abstract

We re-visit the two-agent scheduling on a parallel-batch machine to minimize makespan, where jobs have release dates and linear deteriorating processing times. The objective is to minimize the makespan of agent A with the makespan of agent B being bounded. In the paper Tang, Zhao, Liu, and Leung (2017), the authors reported comprehensive research for this scheduling model. Especially, they presented polynomial-time algorithms for the following four problems. In the first, the batch capacity is unbounded and the two agents are compatible. In the second, the batch capacity is bounded, the two agents are incompatible, the A-jobs have a fixed number of normal processing times, and the B-jobs have a common release date. In the third and forth, the batch capacity is bounded, the two agents are compatible, and the release dates and normal processing times are either agreeable or reversely agreeable. But their discussions for the above four problems are logically confusing. In this paper we present a more efficient polynomial-time algorithm for the first problem and show that the other three problems are NP-hard. We also present a pseudo-polynomial-time algorithm for the version where the batch capacity is bounded, the two agents are incompatible, and A-jobs and B-jobs have their common release dates, respectively. We finally present a strongly polynomial-time algorithm for the version where the batch capacity is unbounded and the two agents are incompatible.