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...