Stochastic bicriteria single machine scheduling with sequence-dependent job attributes and job-dependent learning effects

In real world scheduling systems, task or job attributes are stochastic and sequence dependent, learning improves attributes, and schedulers use their cost (or disutility) functions to evaluate schedules with respect to multiple criteria. This paper addresses a stochastic bicriteria single machine scheduling problem wherein processing times, setup times, and reliabilities/un-reliabilities are random variables that are subjected to different learning effects. Setup times are sequence-dependent, reliabilities/un-reliabilities are either position-dependent or sequence-dependent, and learning effects are job-dependent and position-based. The objective is to find the sequence that minimises the expected value of a cost function of two criteria associated with each sequence. The problem is NP-hard to solve; however, we prove that scenarios wherein cost functions are linear, exponential, and fractional can be modelled as quadratic assignment problems, which are solvable exactly or approximately. We also show that special cases with sequence-independent setup times and either position-independent or sequence-independent reliabilities/un-reliabilities can be solved optimally in polynomial time. Computational results on the scenarios with quadratic assignment formulations show that good solutions can be obtained in a reasonable amount of time. [Received 31 July 2012; Revised 24 October 2012; Accepted 2 January 2013]