Parallel machine scheduling with stochastic release times and processing times - Université d'Évry Access content directly
Journal Articles International Journal of Production Research Year : 2021

Parallel machine scheduling with stochastic release times and processing times

Xin Liu
Chengbin Chu
Ming Liu

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.
No file

Dates and versions

hal-02937348 , version 1 (13-09-2020)

Identifiers

Cite

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, 2021, 59 (20), pp.6327--6346. ⟨10.1080/00207543.2020.1812752⟩. ⟨hal-02937348⟩
110 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More