Optimal assignment of slack due-dates and sequencing of jobs with random processing times on a single machine (Q1178637)

The problem of due date assignment and sequencing of \(n\) independent jobs with random processing times on a single machine is considered. The job processing times \(p_ i\) are mutually independent random variables having distribution functions \(G_ i(p_ i)\) with a finite mean \(\mu_ i\). For each job \(i\) a due date \(d_ i=p_ i+k_ i\) is assigned, where \(k_ i\geq 0\) is waiting allowance. It is assumed that, for a given job sequence \(s\), the due date assignment cost for job \(i\) is \(\varphi(k_ i| s)\) and the missed due date cost of job \(i\) is \(\theta_ i((c_ i-d_ i)^ 2| s)\), where \(c_ i\) is the completion time of job \(i\) under the job sequence \(s\). The aim is to assign due dates \(d_ i\) and to choose a job sequence \(s\) such that the expected value of the total cost for assigned due dates and missed due dates is minimized: \[ E[c(k| s)]=\sum_{i=1}^ n\left\{\varphi_ i(k_ i| s)+\int_ 0^ \infty \int_{p_ i}^ \infty \theta_ i((c_ i-d_ i)^ 2| s)f_ i(p_ i,c_ i)dc_ idp_ i\right\}, \] where \(f_ i(p_ i,c_ i)\) is the joint density function of the processing time and the completion time of job \(i\). In further considerations the author supposes that \(\varphi(k_ i| s)\) and \(\theta_ i((c_ i-d_ i)^ 2| s)\) are linear functions with coefficients \(\alpha_ i>0\) and \(\beta_ i>0\) respectively. For this case the optimal due date assignment is \[ k^*_{[i]}=\sum_{j=1}^{i-1}\mu_{[i]}- \alpha_{[i]}/2\beta_{[i]}, \] where \([i]\) denotes the job in position \(i\) of the job sequence \(s\). For the case \(\alpha_ i=\alpha>0\), \(\beta_ i-\beta>0\) for all \(i\) an \(O(n \log n)\) algorithm for optimal sequence construction is proposed.