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

Yuan Gao, Jinjiang Yuan, C.T. Ng and T.C.E. Cheng

European Journal of Operational Research, 2019, vol. 273, issue 1, 74-81

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.

Keywords: Parallel-batch; Two agents; Release dates; Deterioration (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718306623
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:273:y:2019:i:1:p:74-81

DOI: 10.1016/j.ejor.2018.07.040

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().