Single machine scheduling with step-learning

Matan Atsmony, Baruch Mor () and Gur Mosheiov
Additional contact information
Matan Atsmony: The Hebrew University
Baruch Mor: Ariel University
Gur Mosheiov: The Hebrew University

Journal of Scheduling, 2024, vol. 27, issue 3, No 2, 227-237

Abstract: Abstract In this paper, we study scheduling with step-learning, i.e., a setting where the processing times of the jobs started after their job-dependent learning-dates are reduced. The goal is to minimize makespan on a single machine. We focus first on the case that idle times between consecutive jobs are not allowed. We prove that the problem is NP-hard, implying that no polynomial-time solution exists and, consequently, propose a pseudo-polynomial time dynamic programming algorithm. An extensive numerical study is provided to examine the running time of the algorithm with different learning-dates and job processing time ranges. The special case of a common learning-date for all the jobs is also studied, and a (more efficient) pseudo-polynomial dynamic programming is introduced and tested numerically. In the last part of the paper, the more complicated setting in which idle times are allowed is studied. An appropriate dynamic programming is introduced and tested as well.

Keywords: Scheduling; Single-machine; Step-learning; Job-dependent learning-dates; Dynamic programming (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00763-5 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:27:y:2024:i:3:d:10.1007_s10951-022-00763-5

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

DOI: 10.1007/s10951-022-00763-5

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