Stochastic single machine scheduling problem as a multi-stage dynamic random decision process

Mina Roohnavazfar (), Daniele Manerba (), Lohic Fotio Tiotsop (), Seyed Hamid Reza Pasandideh () and Roberto Tadei ()
Additional contact information
Mina Roohnavazfar: Politecnico di Torino
Daniele Manerba: University of Brescia
Lohic Fotio Tiotsop: Politecnico di Torino
Seyed Hamid Reza Pasandideh: Kharazmi University
Roberto Tadei: Politecnico di Torino

Computational Management Science, 2021, vol. 18, issue 3, No 2, 267-297

Abstract: Abstract In this work, we study a stochastic single machine scheduling problem in which the features of learning effect on processing times, sequence-dependent setup times, and machine configuration selection are considered simultaneously. More precisely, the machine works under a set of configurations and requires stochastic sequence-dependent setup times to switch from one configuration to another. Also, the stochastic processing time of a job is a function of its position and the machine configuration. The objective is to find the sequence of jobs and choose a configuration to process each job to minimize the makespan. We first show that the proposed problem can be formulated through two-stage and multi-stage Stochastic Programming models, which are challenging from the computational point of view. Then, by looking at the problem as a multi-stage dynamic random decision process, a new deterministic approximation-based formulation is developed. The method first derives a mixed-integer non-linear model based on the concept of accessibility to all possible and available alternatives at each stage of the decision-making process. Then, to efficiently solve the problem, a new accessibility measure is defined to convert the model into the search of a shortest path throughout the stages. Extensive computational experiments are carried out on various sets of instances. We discuss and compare the results found by the resolution of plain stochastic models with those obtained by the deterministic approximation approach. Our approximation shows excellent performances both in terms of solution accuracy and computational time.

Keywords: Single machine scheduling; Stochastic sequence-dependent setup times; Stochastic processing times; Learning effect; Deterministic approximation; Multi-stage stochastic programming (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10287-020-00386-1 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:comgts:v:18:y:2021:i:3:d:10.1007_s10287-020-00386-1

Ordering information: This journal article can be ordered from
http://www.springer. ... ch/journal/10287/PS2

DOI: 10.1007/s10287-020-00386-1

Access Statistics for this article

Computational Management Science is currently edited by Ruediger Schultz

More articles in Computational Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().