Minmax scheduling and due-window assignment with position-dependent processing times and job rejection

Gur Mosheiov (), Assaf Sarig and Vitaly Strusevich
Additional contact information
Gur Mosheiov: The Hebrew University
Assaf Sarig: The Hebrew University
Vitaly Strusevich: University of Greenwich

4OR, 2020, vol. 18, issue 4, No 3, 439-456

Abstract: Abstract We study scheduling and due-window assignment problems with the objective function of a minmax type, i.e., the goal is to minimize the largest cost among all scheduled jobs. We assume that the processing times of jobs are position-dependent in the most general way. For a single machine and for a proportionate flow shop environment we present polynomial time solution procedures that are based on solving a linear assignment problem as a subroutine. We further extend the single machine model by allowing job-rejection, provided that the processing times deteriorate, i.e., the position-dependent processing times are non-decreasing functions of the job position. For this setting, the scheduler may decide not to process certain jobs, and each rejected job is penalized accordingly. The problem with the objective that additionally involves a maximum rejection cost component is also shown to be solvable in polynomial time.

Keywords: Scheduling; Sequencing; Due-window assignment; Position-dependent processing times; Proportionate flow shop; Job-rejection; 90B35; 68M20 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-019-00418-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:aqjoor:v:18:y:2020:i:4:d:10.1007_s10288-019-00418-w

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-019-00418-w

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().