Minimising the makespan on parallel identical machines with log-linear position-dependent processing times

Edut Cohen and Dana Shapira

Journal of the Operational Research Society, 2025, vol. 76, issue 3, 581-589

Abstract: This article studies the minimum makespan scheduling problem on parallel identical machines with the log-linear learning/ageing effect, also known as polynomial positional learning/ageing effect. To develop a Fully Polynomial Time Approximation Scheme to the problem, we start with an intermediate artificial variant that rounds the values to integers and restricts the solutions to instances sorted in the shortest/longest processing time order. To this end, we propose a dynamic programming algorithm and show that the difference between its returned value and the minimum makespan of the original problem is independent of the processing times. This then leads to an algorithm with provable guaranteed ϵ-additive approximation and pseudo-polynomial running time algorithm, resulting in the desired fully polynomial time approximation solution to the original, not restricted problem.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2024.2382150 (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:76:y:2025:i:3:p:581-589

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

DOI: 10.1080/01605682.2024.2382150

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