Simheuristic algorithm for a stochastic parallel machine scheduling problem with periodic re-planning assessment

Victor Abu-Marrul (), Rafael Martinelli (), Silvio Hamacher () and Irina Gribkovskaia ()
Additional contact information
Victor Abu-Marrul: Industrial Engineering Department – Pontifical Catholic University of Rio de Janeiro (PUC-Rio)
Rafael Martinelli: Industrial Engineering Department – Pontifical Catholic University of Rio de Janeiro (PUC-Rio)
Silvio Hamacher: Industrial Engineering Department – Pontifical Catholic University of Rio de Janeiro (PUC-Rio)
Irina Gribkovskaia: Molde University College - Specialized University in Logistics (HiMolde)

Annals of Operations Research, 2023, vol. 320, issue 2, No 2, 547-572

Abstract: Abstract This paper addresses a parallel machine scheduling problem with non-anticipatory family setup times and batching, considering the task’s stochastic processing times and release dates. The problem arises from a real-life ship scheduling problem in the oil and gas industry. We developed an Iterated Greedy simheuristic with built-in Monte Carlo Simulation to sample the stochastic parameters. We conducted experiments on a set of instances from the literature, considering two simheuristic variants and three uncertainty levels for the stochastic parameters. To highlight the advantages of using simulation to tackle the stochastic problem, the simheuristics are compared against a regular Iterated Greedy metaheuristic, yielding an improvement of up to 16.5% on the objective function’s expected values, with a reduced impact on computational times. During a risk analysis, the Pareto set of solutions is generated to illustrate the trade-off between the expected objective value of the solutions and the conditional value at risk, providing decision-makers with a useful tool to select the schedules that better fit their risk profiles. We use an iterative mechanism to build confidence intervals within a certain confidence level during the method’s simulation step, interrupting the procedure when it reaches the desired error. This strategy’s advantage is highlighted in the computational experiments, which indicates that the number of replications of the simulation is instance and uncertainty level dependent. A periodic re-planning strategy is also used to evaluate the performance of the simheuristic, highlighting the advantages of using the proposed algorithm in a real-life usage situation.

Keywords: Simulation-optimization; Parallel machine scheduling; Family scheduling; Offshore resource management; Batch scheduling (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-022-04534-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:annopr:v:320:y:2023:i:2:d:10.1007_s10479-022-04534-5

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

DOI: 10.1007/s10479-022-04534-5

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

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