Single-machine scheduling of multiple projects with controllable processing times

Zhichao Geng and Jinjiang Yuan

European Journal of Operational Research, 2023, vol. 308, issue 3, 1074-1090

Abstract: This paper studies the single-machine multiple-project scheduling problem with controllable processing times, in which the cost of a project refers to the total compression cost of its jobs plus the weighted number of tardy jobs in a schedule satisfying some given precedence constraints. It involves four specific problems: (i) minimizing the total cost of an arbitrary number of projects, (ii) being the same as (i) except the jobs from the same project having a common due date, (iii) having a fixed number of projects and minimizing the cost of one project subject to the cost of each of other projects not exceeding a given threshold, and (iv) being the same as (iii) except all jobs having identical weights. We show that a special version of (i) in which each project has only two jobs and all jobs have unit weights and cannot be compressed is strongly NP-hard (it implies the strong NP-hardness of (i)), (ii) is weakly NP-hard and admits a pseudo-polynomial algorithm and a fully polynomial time approximation scheme, (iii) is pseudo-polynomially solvable by a two-phase transformation, and (iv) is weakly NP-hard even if there are only two projects and all jobs have identical maximum compression amounts and identical processing times.

Keywords: Scheduling; Controllable processing times; Multiple projects; Compression cost; Pseudo-polynomial algorithm (search for similar items in EconPapers)
Date: 2023
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/S0377221723000449
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:308:y:2023:i:3:p:1074-1090

DOI: 10.1016/j.ejor.2023.01.026

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 ().