A note on a single-shift days-off scheduling problem with sequence-dependent labor costs

Eiji Mizutani () and Kevin Alexander Sánchez Galeano ()
Additional contact information
Eiji Mizutani: National Taiwan University of Science and Technology
Kevin Alexander Sánchez Galeano: National Taiwan University of Science and Technology

Journal of Scheduling, 2023, vol. 26, issue 3, No 5, 315-329

Abstract: Abstract Elshafei and Alfares have developed a dynamic programming (DP) algorithm for minimizing the total sequence-dependent cost in a constrained single-shift days-off scheduling problem. In general, however, their proposed DP algorithm may not obtain an optimal solution unlike their claim; in their highlighted security personnel scheduling example, we show how to improve their alleged optimal schedule just by inspection. The purpose of this paper is to describe better solution approaches to their challenging sequence-dependent workforce scheduling problem. We first explain why their DP algorithm encounters difficulties in finding an optimal solution with emphasis on the importance of proper state description for DP. We then describe how to correct their DP procedure with minimal effort. After that, we confirm such a better scheduling result by solving an associated mathematical programming problem with the Gurobi Optimizer, a widely recognized mathematical programming solver.

Keywords: Dynamic programming; Days-off scheduling problem; Sequence- dependent labor costs; Traveling salesperson problem (TSP) (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00749-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jsched:v:26:y:2023:i:3:d:10.1007_s10951-022-00749-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-022-00749-3

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().