Scheduling with or without precedence relations on a serial-batch machine to minimize makespan and maximum cost

Zhichao Geng, Jinjiang Yuan and Junling Yuan

Applied Mathematics and Computation, 2018, vol. 332, issue C, 1-18

Abstract: In this paper, we consider several scheduling problems on a serial-batch machine for scheduling jobs with or without precedence relations. Under the serial-batch setting, the jobs in a batch are processed in succession and are removed until the last job in this batch finishes its processing. Thus, the processing time of a batch is equal to the sum of processing times of jobs in the batch. When a new batch starts, a constant setup time is required for the machine. The objectives of the problems involve minimizing makespan and a maximum cost. For these problems, we either present polynomial-time algorithms to generate all Pareto optimal points and find a corresponding Pareto optimal schedule for each Pareto optimal point, or give the strong NP-hardness proof. Experimentation results show that the proposed algorithms for the considered problems are very efficient.

Keywords: Scheduling; Pareto optimization; Serial-batch; Maximum cost; Makespan (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300318301668
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:apmaco:v:332:y:2018:i:c:p:1-18

DOI: 10.1016/j.amc.2018.03.001

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().