Bi-objective single machine scheduling problem with stochastic processing times

Abstract

In this study, a static single machine scheduling problem is investigated, where processing times are stochastic, due dates are deterministic and inserted idle time is allowed. Two objective functions are simultaneously taken into account, minimization of mean completion time and minimization of earliness and tardiness costs. A robust model is presented to tackle the problem, based on goal programming and a stochastic programming model named E-model. The proposed model not only obtains optimal operating systems, but also considers the variance of the objective functions and the correlation between them. Moreover, chance-constrained programming model is used to take into account the randomness in the constraints of the model. The model is presented with general distribution of processing times and the normal case is explored in experiments. Two sets of computational experiments are presented to test the efficiency of the proposed model. In the first set, the performance obtained by the bi-objective formulation is measured, where in the second set the performance obtained by incorporating robustness is measured. Results confirm the effectiveness of the proposed model, in both directions.

Appendix: Definition of Equation (27)

We have: $C_1 =I_1 +\mathop \sum \limits _{j=1}^n Y_{j1} p_j$ and $C_k =I_k +C_{k-1} +\mathop \sum \limits _{j=1}^n Y_{jk} p_j (k=2,3,\ldots ,n)$

So,

$$\begin{aligned}&C_1 =I_1 +\mathop \sum \limits _{j=1}^n Y_{j1} p_j\\&C_2 =I_2 +\left( {I_1 +\mathop \sum \limits _{j=1}^n Y_{j1} p_j }\right) +\mathop \sum \limits _{j=1}^n Y_{j2} p_j\\&C_3 =I_3 +\left( {I_2 +I_1 +\mathop \sum \limits _{j=1}^n Y_{j1} p_j +\mathop \sum \limits _{j=1}^n Y_{j2} p_j }\right) +\mathop \sum \limits _{j=1}^n Y_{j3} p_j\\&\cdots \\&C_{n-1} =I_{n-1} {+}\left( {I_{n-2} {+}\cdots {+}I_1 {+}\mathop \sum \limits _{j=1}^n Y_{j1} p_j {+}\cdots {+}\mathop \sum \limits _{j=1}^n Y_{j,n-2} p_j }\right) {+}\mathop \sum \limits _{j=1}^n Y_{j,n-1} p_j\\&C_n =I_n +\left( {I_{n-1} +\cdots +I_1 +\mathop \sum \limits _{j=1}^n Y_{j1} p_j +\cdots +\mathop \sum \limits _{j=1}^n Y_{j,n-1} p_j }\right) +\mathop \sum \limits _{j=1}^n Y_{jn} p_j \end{aligned}$$

Therefore,

$$\begin{aligned} \mathop \sum \limits _{k=1}^n C_k&=C_1 {+}C_2 {+}\cdots {+}C_n =n\left( {I_1 {+}\mathop \sum \limits _{j=1}^n Y_{j1} p_j }\right) \\&\quad +\,( {n-1})\left( {I_2 +\mathop \sum \limits _{j=1}^n Y_{j2} p_j }\right) +\cdots +2\left( {I_{n-1} +\mathop \sum \limits _{j=1}^n Y_{j,n-1} p_j }\right) \\&\quad +\,1\left( {I_n +\mathop \sum \limits _{j=1}^n Y_{jn} p_j }\right) =\mathop \sum \limits _{k=1}^n \left( {( {n-k+1})\left( {I_k +\left( {\mathop \sum \limits _{j=1}^n Y_{jk} p_j }\right) }\right) }\right) \\ \end{aligned}$$