Skip to Main content Skip to Navigation
Journal articles

Parallel machine scheduling with stochastic release times and processing times

Abstract : Stochastic scheduling has received much attention from both industry and academia. Existing works usually focus on random job processing times. However, the uncertainty existing in job release times may largely impact the performance as well. This work investigates a stochastic parallel machine scheduling problem, where job release times and processing times are uncertain. The problem consists of a two-stage decision-making process: (i) assigning jobs to machines on the first stage before the realisation of uncertain parameters (job release times and processing times) and (ii) scheduling jobs on the second stage given the job-to-machine assignment and the realisation of uncertain parameters. The objective is to minimise the total cost, including the setup cost on machines (induced by job-to-machine assignment) and the expected penalty cost of jobs' earliness and tardiness. A two-stage stochastic program is proposed, and the sample average approximation (SAA) method is applied. A scenario-reduction-based decomposition approach is further developed to improve the computational efficiency. Numerical results show that the scenario-reduction-based decomposition approach performs better than the SAA, in terms of solution quality and computation time.
Document type :
Journal articles
Complete list of metadatas
Contributor : Frédéric Davesne <>
Submitted on : Sunday, September 13, 2020 - 4:23:03 PM
Last modification on : Tuesday, September 15, 2020 - 3:27:44 AM



Xin Liu, Feng Chu, Feifeng Zheng, Chengbin Chu, Ming Liu. Parallel machine scheduling with stochastic release times and processing times. International Journal of Production Research, Taylor & Francis, In press, pp.1-20. ⟨10.1080/00207543.2020.1812752⟩. ⟨hal-02937348⟩



Record views