Scheduling with regular performance measures and optional job rejection on a single machine

Baruch Mor and Dana Shapira

Journal of the Operational Research Society, 2020, vol. 71, issue 8, 1315-1325

Abstract: We address single machine problems with optional job rejection, and focus on minimizing regular performance measures, ie, functions that are non-decreasing in the jobs, completion times, subject to the constraint that the total rejection cost cannot exceed a predefined upper bound. Our contribution is twofold. First, we consider two problems that, to the best of our knowledge, were not addressed in scheduling theory – total (unweighted) tardiness with a common due date and total weighted tardiness with a common due date. For these problems, we show that they are NP-hard and present pseudo-polynomial-time dynamic programming (DP) solution algorithms. Second, we revisit three problems: makespan with release-dates, total completion time, and total weighted completion time, and present enhanced DP solution algorithms. To all studied problems, we provide extensive numerical studies, verifying their efficiency, subsequently demonstrating both theoretical and practical enhancement.

Date: 2020
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2019.1621222 (text/html)
Access to full text is restricted to subscribers.

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:taf:tjorxx:v:71:y:2020:i:8:p:1315-1325

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2019.1621222

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().