Theoretical and practical issues in single-machine scheduling with two job release and delivery times

Alejandro Reynoso and Nodari Vakhania ()
Additional contact information
Alejandro Reynoso: Centro de Investigación en Ciencias, UAEMor
Nodari Vakhania: Centro de Investigación en Ciencias, UAEMor

Journal of Scheduling, 2021, vol. 24, issue 6, No 4, 615-647

Abstract: Abstract We study a single-machine scheduling problem with two allowable job release and delivery times. This special case of a strongly NP-hard single-machine scheduling problem with an arbitrary number of job release and delivery times and with the objective to minimize the maximum job completion time remains NP-hard. Nevertheless, it is more transparent and accessible than the general version. Hence, it permitted us to establish some nice properties that yielded simple and efficient solution methods. On the one hand, the restricted setting is useful by its own right since it fits some real-life applications. On the other hand, the presented case study is helpful in the solution of a more general setting with a constant number of job release and delivery times. In particular, the optimality conditions and the heuristics methods that we propose here for the restricted setting might be generalized to the extended setting. The established optimality criteria are explicit conditions under which the restricted problem can be solved optimally in time $$O(n\log n)$$ O ( n log n ) . The extensive computational study showed that at least one of these conditions is satisfied for practically all the randomly generated 50 million problem instances while applying our heuristics to these instances. We report a favorable practical performance of our polynomial-time subroutine that invokes our five heuristics and verifies the proposed optimality conditions consecutively. These conditions were verified for the solutions delivered by the five heuristics individually and in a combined fashion as four pairs of heuristics and as all the five heuristics together. Fifty million problem instances were randomly generated using uniform distribution for each of these ten combinations. For the 50 million instances generated for the last (overall) combination, the schedule created by at least one of the heuristics has satisfied at least one of our optimality conditions (so all these problem instances were solved optimally). We also addressed the (theoretical) possibility that none of our conditions is satisfied, and showed how a known dynamic programming algorithm for SUBSET SUM problem can be used for the solution of the scheduling problem in pseudo-polynomial time. For a considerable part of the tested instances, one of the five scheduling heuristics has solved optimally also SUBSET SUM problem.

Keywords: Polynomial and pseudo-polynomial time algorithms; SUBSET SUM; Single-machine scheduling; Release time; Delivery time; Time complexity (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-021-00708-4 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:jsched:v:24:y:2021:i:6:d:10.1007_s10951-021-00708-4

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-021-00708-4

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

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