THE EQUIVALENCE OF GENERAL SET-COVERING AND IMPLICIT INTEGER PROGRAMMING FORMULATIONS FOR SHIFT SCHEDULING

Citation
Se. Bechtold et Lw. Jacobs, THE EQUIVALENCE OF GENERAL SET-COVERING AND IMPLICIT INTEGER PROGRAMMING FORMULATIONS FOR SHIFT SCHEDULING, Naval research logistics, 43(2), 1996, pp. 233-249
Citations number
25
Categorie Soggetti
Operatione Research & Management Science","Operatione Research & Management Science","Engineering, Marine
Journal title
ISSN journal
0894069X
Volume
43
Issue
2
Year of publication
1996
Pages
233 - 249
Database
ISI
SICI code
0894-069X(1996)43:2<233:TEOGSA>2.0.ZU;2-0
Abstract
In a recent article we demonstrated that implicit optimal modeling for shift scheduling(P2) has inherent size and execution time advantages over the general set-covering formulation for shift scheduling (Pi) [1 1, 13]. We postulated that the absence of extraordinary overlap (EO) w as a requirement for the equivalence of PI and P2. We have defined EO as the condition in which the earliest and latest starts for a break i n one shift are earlier and later than the earliest and latest starts for a break in any other shift(s). In this article, we prove that our earlier postulate was accurate. Additionally, we discuss research exte nsions and note other scheduling problems for which implicit modeling may be appropriate. (C) 1996 John Wiley & Sons, Inc.