Stochastic bicriteria single machine scheduling with sequence-dependent job attributes and job-dependent learning effects
by H.M. Soroush
European J. of Industrial Engineering (EJIE), Vol. 8, No. 4, 2014

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]

Online publication date: Sat, 11-Oct-2014

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the European J. of Industrial Engineering (EJIE):
Login with your Inderscience username and password:

    Username:        Password:         

Forgotten your password?


Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com