On the Complexity of Manpower Shift Scheduling

• 主要作者: LAU, Hoong Chuin
• 格式: text
• 語言: English
• 出版: Institutional Knowledge at Singapore Management University 1996
• 主題: Numerical Analysis and Scientific Computing; Operations Research, Systems Engineering and Industrial Engineering
• 在線閱讀: https://ink.library.smu.edu.sg/sis_research/37; https://ink.library.smu.edu.sg/context/sis_research/article/1036/viewcontent/cor96.pdf
• 機構: Singapore Management University

We consider the shift assignment problem in manpower scheduling, and show that a restricted version of it is NP-hard by a reduction from 3SAT. We then present polynomial algorithms to solve special cases of the problem and show how they can be deployed to solve more complex versions of the shift ass...