A grasp-knapsack hybrid for a nurse-scheduling problem

This paper is concerned with the application of a GRASP approach to a nurse-scheduling problem in which the objective is to optimise a set of preferences subject to a set of binding constraints. The balance between feasibility and optimality is a key issue. This is addressed by using a knapsack mode...

Full description

Saved in:
Bibliographic Details
Published in:Journal of heuristics 2009-08, Vol.15 (4), p.351-379
Main Authors: Goodman, Melissa D., Dowsland, Kathryn A., Thompson, Jonathan M.
Format: Article
Language:English
Subjects:
Artificial Intelligence
Calculus of Variations and Optimal Control
Optimization
Feasibility
Genetic algorithms
Heuristic
Management Science
Mathematical programming
Mathematics
Mathematics and Statistics
Neighborhoods
Nurses
Operations Research
Operations Research/Decision Theory
Scheduling
Shift work
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c346t-3469103b406a97a915dcb5aeed9a365cdf1bce6ea16616cd6cf4147b35aa96613
cites cdi_FETCH-LOGICAL-c346t-3469103b406a97a915dcb5aeed9a365cdf1bce6ea16616cd6cf4147b35aa96613
container_end_page 379
container_issue 4
container_start_page 351
container_title Journal of heuristics
container_volume 15
creator Goodman, Melissa D.
Dowsland, Kathryn A.
Thompson, Jonathan M.
description This paper is concerned with the application of a GRASP approach to a nurse-scheduling problem in which the objective is to optimise a set of preferences subject to a set of binding constraints. The balance between feasibility and optimality is a key issue. This is addressed by using a knapsack model to ensure that the solutions produced by the construction heuristic are easy to repair. Several construction heuristics and neighbourhoods are compared empirically. The best combination is further enhanced by a diversification strategy and a dynamic evaluation criterion. Tests show that it outperforms previously published approaches and finds optimal solutions quickly and consistently.
doi_str_mv 10.1007/s10732-007-9066-7
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_199297723</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>1753304851</sourcerecordid><originalsourceid>FETCH-LOGICAL-c346t-3469103b406a97a915dcb5aeed9a365cdf1bce6ea16616cd6cf4147b35aa96613</originalsourceid><addsrcrecordid>eNp1ULtOwzAUtRBIlMIHsEXsBl87seuxqnhJlVhgtq4dJ02bJsFuhv49jsLAwnLv0dF5SIeQe2CPwJh6isCU4DRBqpmUVF2QBRSKUy20ukxYrIACF3BNbmLcM8b0qhALItdZHTAO9NDhENEdst3ZhqbMqj5kmHVjiJ5Gt_Pl2DZdnQ2ht60_3pKrCtvo737_kny9PH9u3uj24_V9s95SJ3J5ouloYMLmTKJWqKEonS3Q-1KjkIUrK7DOS48gJUhXSlflkCsrCkSdKLEkD3Nu6v0efTyZfT-GLlUa0JprpbhIIphFLvQxBl-ZITRHDGcDzEzrmHkdM8FpHaOSh8-emLRd7cOf4H9NP2e_ZrA</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>199297723</pqid></control><display><type>article</type><title>A grasp-knapsack hybrid for a nurse-scheduling problem</title><source>ABI/INFORM global</source><source>Springer Nature</source><creator>Goodman, Melissa D. ; Dowsland, Kathryn A. ; Thompson, Jonathan M.</creator><creatorcontrib>Goodman, Melissa D. ; Dowsland, Kathryn A. ; Thompson, Jonathan M.</creatorcontrib><description>This paper is concerned with the application of a GRASP approach to a nurse-scheduling problem in which the objective is to optimise a set of preferences subject to a set of binding constraints. The balance between feasibility and optimality is a key issue. This is addressed by using a knapsack model to ensure that the solutions produced by the construction heuristic are easy to repair. Several construction heuristics and neighbourhoods are compared empirically. The best combination is further enhanced by a diversification strategy and a dynamic evaluation criterion. Tests show that it outperforms previously published approaches and finds optimal solutions quickly and consistently.</description><identifier>ISSN: 1381-1231</identifier><identifier>EISSN: 1572-9397</identifier><identifier>DOI: 10.1007/s10732-007-9066-7</identifier><language>eng</language><publisher>Boston: Springer US</publisher><subject>Artificial Intelligence ; Calculus of Variations and Optimal Control; Optimization ; Feasibility ; Genetic algorithms ; Heuristic ; Management Science ; Mathematical programming ; Mathematics ; Mathematics and Statistics ; Neighborhoods ; Nurses ; Operations Research ; Operations Research/Decision Theory ; Scheduling ; Shift work ; Studies</subject><ispartof>Journal of heuristics, 2009-08, Vol.15 (4), p.351-379</ispartof><rights>Springer Science+Business Media, LLC 2007</rights><rights>Springer Science+Business Media, LLC 2009</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c346t-3469103b406a97a915dcb5aeed9a365cdf1bce6ea16616cd6cf4147b35aa96613</citedby><cites>FETCH-LOGICAL-c346t-3469103b406a97a915dcb5aeed9a365cdf1bce6ea16616cd6cf4147b35aa96613</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/199297723/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$H</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/199297723?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,776,780,11667,27901,27902,36037,44339,74638</link.rule.ids></links><search><creatorcontrib>Goodman, Melissa D.</creatorcontrib><creatorcontrib>Dowsland, Kathryn A.</creatorcontrib><creatorcontrib>Thompson, Jonathan M.</creatorcontrib><title>A grasp-knapsack hybrid for a nurse-scheduling problem</title><title>Journal of heuristics</title><addtitle>J Heuristics</addtitle><description>This paper is concerned with the application of a GRASP approach to a nurse-scheduling problem in which the objective is to optimise a set of preferences subject to a set of binding constraints. The balance between feasibility and optimality is a key issue. This is addressed by using a knapsack model to ensure that the solutions produced by the construction heuristic are easy to repair. Several construction heuristics and neighbourhoods are compared empirically. The best combination is further enhanced by a diversification strategy and a dynamic evaluation criterion. Tests show that it outperforms previously published approaches and finds optimal solutions quickly and consistently.</description><subject>Artificial Intelligence</subject><subject>Calculus of Variations and Optimal Control; Optimization</subject><subject>Feasibility</subject><subject>Genetic algorithms</subject><subject>Heuristic</subject><subject>Management Science</subject><subject>Mathematical programming</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Neighborhoods</subject><subject>Nurses</subject><subject>Operations Research</subject><subject>Operations Research/Decision Theory</subject><subject>Scheduling</subject><subject>Shift work</subject><subject>Studies</subject><issn>1381-1231</issn><issn>1572-9397</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2009</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNp1ULtOwzAUtRBIlMIHsEXsBl87seuxqnhJlVhgtq4dJ02bJsFuhv49jsLAwnLv0dF5SIeQe2CPwJh6isCU4DRBqpmUVF2QBRSKUy20ukxYrIACF3BNbmLcM8b0qhALItdZHTAO9NDhENEdst3ZhqbMqj5kmHVjiJ5Gt_Pl2DZdnQ2ht60_3pKrCtvo737_kny9PH9u3uj24_V9s95SJ3J5ouloYMLmTKJWqKEonS3Q-1KjkIUrK7DOS48gJUhXSlflkCsrCkSdKLEkD3Nu6v0efTyZfT-GLlUa0JprpbhIIphFLvQxBl-ZITRHDGcDzEzrmHkdM8FpHaOSh8-emLRd7cOf4H9NP2e_ZrA</recordid><startdate>20090801</startdate><enddate>20090801</enddate><creator>Goodman, Melissa D.</creator><creator>Dowsland, Kathryn A.</creator><creator>Thompson, Jonathan M.</creator><general>Springer US</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>8AL</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8FL</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>L.-</scope><scope>M0C</scope><scope>M0N</scope><scope>P5Z</scope><scope>P62</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PYYUZ</scope><scope>Q9U</scope></search><sort><creationdate>20090801</creationdate><title>A grasp-knapsack hybrid for a nurse-scheduling problem</title><author>Goodman, Melissa D. ; Dowsland, Kathryn A. ; Thompson, Jonathan M.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c346t-3469103b406a97a915dcb5aeed9a365cdf1bce6ea16616cd6cf4147b35aa96613</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2009</creationdate><topic>Artificial Intelligence</topic><topic>Calculus of Variations and Optimal Control; Optimization</topic><topic>Feasibility</topic><topic>Genetic algorithms</topic><topic>Heuristic</topic><topic>Management Science</topic><topic>Mathematical programming</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Neighborhoods</topic><topic>Nurses</topic><topic>Operations Research</topic><topic>Operations Research/Decision Theory</topic><topic>Scheduling</topic><topic>Shift work</topic><topic>Studies</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Goodman, Melissa D.</creatorcontrib><creatorcontrib>Dowsland, Kathryn A.</creatorcontrib><creatorcontrib>Thompson, Jonathan M.</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>ABI-INFORM Complete</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>ProQuest Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central Korea</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer Science Database</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ABI/INFORM global</collection><collection>Computing Database</collection><collection>ProQuest advanced technologies &amp; aerospace journals</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>One Business (ProQuest)</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ABI/INFORM Collection China</collection><collection>ProQuest Central Basic</collection><jtitle>Journal of heuristics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Goodman, Melissa D.</au><au>Dowsland, Kathryn A.</au><au>Thompson, Jonathan M.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A grasp-knapsack hybrid for a nurse-scheduling problem</atitle><jtitle>Journal of heuristics</jtitle><stitle>J Heuristics</stitle><date>2009-08-01</date><risdate>2009</risdate><volume>15</volume><issue>4</issue><spage>351</spage><epage>379</epage><pages>351-379</pages><issn>1381-1231</issn><eissn>1572-9397</eissn><abstract>This paper is concerned with the application of a GRASP approach to a nurse-scheduling problem in which the objective is to optimise a set of preferences subject to a set of binding constraints. The balance between feasibility and optimality is a key issue. This is addressed by using a knapsack model to ensure that the solutions produced by the construction heuristic are easy to repair. Several construction heuristics and neighbourhoods are compared empirically. The best combination is further enhanced by a diversification strategy and a dynamic evaluation criterion. Tests show that it outperforms previously published approaches and finds optimal solutions quickly and consistently.</abstract><cop>Boston</cop><pub>Springer US</pub><doi>10.1007/s10732-007-9066-7</doi><tpages>29</tpages></addata></record>
fulltext fulltext
identifier ISSN: 1381-1231
ispartof Journal of heuristics, 2009-08, Vol.15 (4), p.351-379
issn 1381-1231
1572-9397
language eng
recordid cdi_proquest_journals_199297723
source ABI/INFORM global; Springer Nature
subjects Artificial Intelligence
Calculus of Variations and Optimal Control
Optimization
Feasibility
Genetic algorithms
Heuristic
Management Science
Mathematical programming
Mathematics
Mathematics and Statistics
Neighborhoods
Nurses
Operations Research
Operations Research/Decision Theory
Scheduling
Shift work
Studies
title A grasp-knapsack hybrid for a nurse-scheduling problem
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-31T08%3A02%3A35IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20grasp-knapsack%20hybrid%20for%20a%20nurse-scheduling%20problem&rft.jtitle=Journal%20of%20heuristics&rft.au=Goodman,%20Melissa%20D.&rft.date=2009-08-01&rft.volume=15&rft.issue=4&rft.spage=351&rft.epage=379&rft.pages=351-379&rft.issn=1381-1231&rft.eissn=1572-9397&rft_id=info:doi/10.1007/s10732-007-9066-7&rft_dat=%3Cproquest_cross%3E1753304851%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c346t-3469103b406a97a915dcb5aeed9a365cdf1bce6ea16616cd6cf4147b35aa96613%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=199297723&rft_id=info:pmid/&rfr_iscdi=true