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

Authors: H.M. Soroush

Addresses: Department Statistics and Operations Research, College of Science, Kuwait University, P.O. Box 5969, Safat 13060, Kuwait

Abstract: 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]

Keywords: stochastic job attributes; bicriteria scheduling; single machine scheduling; sequence-dependent job attributes; job-dependent learning; setup times; reliability; learning effects; modelling; quadratic assignment.

DOI: 10.1504/EJIE.2014.064754

European Journal of Industrial Engineering, 2014 Vol.8 No.4, pp.421 - 456

Published online: 14 Sep 2014 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article