Improving computational efficiency in tree search methods for scheduling: A statistical approach

King, JR and As Spachis

Omega, 1980, vol. 8, issue 6, 655-660

Abstract: The paper examines how the computational efficiency of tree search applied to job-shop scheduling problems may be improved by a statistical method which provides both a bound and stopping rule for the search process. The Weibull distribution is used as the limiting form of the frequency distribution of the smallest members of samples of feasible job-shop schedules. Estimates of the optimal solution are obtained by calculating the most likely value of the Weibull location parameter, allowing a tight bracket for the optimal makespan value to be established. Estimates of the optimal solution of sub-problems with fixed partial sequence are proposed as approximate lower bounds for a 'best-bound' search strategy.

Date: 1980
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/0305-0483(80)90007-9
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:8:y:1980:i:6:p:655-660

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 ().