Multi-scenario scheduling to maximise the weighted number of just-in-time jobs

Miri Gilenson and Dvir Shabtay

Journal of the Operational Research Society, 2021, vol. 72, issue 8, 1762-1779

Abstract: We study a multi-scenario scheduling problem on a single-machine and a two-machine flow-shop system. The criterion is to maximise the weighted number of just-in-time jobs. We first analyze the case where only processing times are scenario-dependent. For this case, we prove that the single-machine problem is solvable in polynomial time. We also prove that the unit weight two-machine flow-shop problem is solvable in polynomial time if processing times are scenario-dependent only on the second machine, and is ordinary NP-hard when processing times are scenario-dependent only on the first machine. This ordinary NP-hard result holds as long as the number of scenarios is fixed. Otherwise, the problem becomes strongly NP-hard. We then analyze the case where only weights are scenario-dependent. We adopt a multi-criteria approach and define several problem variations. We prove that one of them is polynomial solvable on a single machine and ordinary NP-hard in a two-machine flow-shop system. We also prove that all other problem variations are ordinary NP-hard even if there are only two scenarios, and are strongly NP-hard when the number of scenarios is arbitrary. Finally, we provide two pseudo-polynomial time algorithms for solving all the hard problems when the number of scenarios is fixed.

Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2019.1578628 (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:72:y:2021:i:8:p:1762-1779

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

DOI: 10.1080/01605682.2019.1578628

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