Polynomial-time solutions for minimizing total load on unrelated machines with position-dependent processing times and rate-modifying activities

Baruch Mor (), Gur Mosheiov and Dvir Shabtay
Additional contact information
Baruch Mor: Ariel University
Gur Mosheiov: The Hebrew University
Dvir Shabtay: Ben-Gurion University of the Negev

Journal of Scheduling, 2025, vol. 28, issue 4, No 1, 377-390

Abstract: Abstract We study the problem of minimizing total load on parallel unrelated machines. Job processing times are assumed to be machine- and position-dependent in the most general way. The scheduler may perform a rate-modifying maintenance activity on each machine. The processing times of the jobs scheduled after the maintenance are reduced. The maintenance time and the impact on the following jobs are machine-dependent. We introduce a solution algorithm which is polynomial when a constant bounds the number of machines. The special case of (general) job deterioration, the more general case in which job rejection is allowed, and the extension to the setting of job processing times, which are controllable through allocating a limited resource, are also studied. All these scheduling problems are shown to be solved in polynomial time.

Keywords: Scheduling; Unrelated machines; Total load; Position-dependent processing times; Rate-modifying activity; Job deterioration; Job rejection (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-025-00848-x 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:28:y:2025:i:4:d:10.1007_s10951-025-00848-x

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

DOI: 10.1007/s10951-025-00848-x

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