Sequencing with uncertain numerical data for makespan minimisation

Lai T-C and Y N Sotskov
Additional contact information
Lai T-C: National Taiwan University
Y N Sotskov: Belarusian Academy of Sciences

Journal of the Operational Research Society, 1999, vol. 50, issue 3, 230-243

Abstract: Abstract We consider a scheduling problem with the objective of minimising the makespan under uncertain numerical input data (for example, the processing time of an operation, the job release time and due date) and fixed structural input data (for example the precedence and capacity constraints). We assume that at (before) the scheduling stage the structural input data are known and fixed but all we know about the numerical input data are their upper and lower bounds, where the uncertain numerical data become realised at the control stage as the scheduled process evolves. After improving the mixed graph model, we present an approach for dealing with our scheduling problem under uncertain numerical data based on a stability analysis of an optimal makespan schedule. In particular, we investigate the candidate set of the critical paths in a circuit-free digraph, characterise a minimal set of the optimal schedules, and develop an optimal and a heuristic algorithm. We also report computational results for randomly generated as well as well-known test problems.

Keywords: makespan; mixed graph; optimal scheduling; uncertainty (search for similar items in EconPapers)
Date: 1999
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2600690 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:50:y:1999:i:3:d:10.1057_palgrave.jors.2600690

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2600690

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().