An approach to solve a hierarchical stochastic sequential ordering problem

David Alcaide, Andrés Rodriguez-Gonzalez and Joaquín Sicilia

Omega, 2003, vol. 31, issue 3, 169-187

Abstract: In this paper, we study a stochastic sequential ordering problem, where a set of jobs must be scheduled on a single machine. The jobs have stochastic processing times and verify certain precedence relations. For each job, there also exists a time window characterized by the release time and the due date. The jobs must be processed into the time-windows. For all the sequences of jobs that verify the precedence relations and the release times, the feasibility probability of a sequence it is defined as the probability that the sequence heeds the due dates. The problem consists of finding a sequence of jobs with the minimum expected makespan among the sequences with maximum feasibility probability. We prove that this problem is NP-hard and we propose an algorithm to find an approximate solution for this problem. The algorithm does not depend on the distribution types of the random input data considered. This procedure looks first for sequences of jobs with a high probability of being feasible. Next, the algorithm selects, among the sequences which have an acceptable feasibility probability level, that sequence with minimum expected makespan. Computational experiences are also reported, and the results show us that the proposed algorithm finds good solutions with short CPU times.

Keywords: Stochastic; scheduling; Sequential; ordering; problem; Makespan (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305-0483(03)00027-6
Full text for ScienceDirect subscribers only

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:eee:jomega:v:31:y:2003:i:3:p:169-187

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().