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, T. C.E. Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

16 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)74-81
Number of pages8
JournalEuropean Journal of Operational Research
Volume273
Issue number1
DOIs
Publication statusPublished - 16 Feb 2019

Keywords

  • Deterioration
  • Parallel-batch
  • Release dates
  • Two agents

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this