Algorithms for handling soft constraints and their applications to staff scheduling problems

Qi Zhao and Randy Goebel

Intelligent Systems in Accounting, Finance and Management, 1999, vol. 8, issue 2, 119-129

Abstract: This paper presents a new model for dynamically deciding when, how, and to what extent soft constraints should be relaxed. The first part of the model is a depth‐first search algorithm and a best‐first repair algorithm which can generate partial schedules quickly. The second part is an iterative relaxation algorithm which can augment the generated partial schedules by slightly relaxing potentially relaxable constraints (i.e. soft constraints). The model guarantees that (1) a soft constraint will be relaxed only when no backtrack (repair) can be made within a time limit, (2) the relaxation of soft constraints can always deepen the search tree, and (3) the relaxation will only be made at dead nodes, and when the search algorithm can be continued the relaxed soft constraints will return to their initial states. The model has been successfully applied to two staff scheduling problems, dispatcher scheduling problem and crew scheduling problem. Copyright © 1999 John Wiley & Sons, Ltd.

Date: 1999
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/(SICI)1099-1174(199906)8:23.0.CO;2-N

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:wly:isacfm:v:8:y:1999:i:2:p:119-129

Ordering information: This journal article can be ordered from
http://www.blackwell ... bs.asp?ref=1099-1174

Access Statistics for this article

More articles in Intelligent Systems in Accounting, Finance and Management from John Wiley & Sons, Ltd.
Bibliographic data for series maintained by Wiley Content Delivery ().