On the Complexity of Manpower Shift Scheduling
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...
Saved in:
| Main Author: | |
|---|---|
| Format: | text |
| Language: | English |
| Published: |
Institutional Knowledge at Singapore Management University
1996
|
| Subjects: | |
| Online Access: | https://ink.library.smu.edu.sg/sis_research/37 https://ink.library.smu.edu.sg/context/sis_research/article/1036/viewcontent/cor96.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Singapore Management University |
| Language: | English |
| id |
sg-smu-ink.sis_research-1036 |
|---|---|
| record_format |
dspace |
| spelling |
sg-smu-ink.sis_research-10362018-05-18T07:01:17Z On the Complexity of Manpower Shift Scheduling LAU, Hoong Chuin 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 assignment problem. Our work formally defines the computational intractibility of manpower shift scheduling and thus justifies existing works in developing manpower scheduling systems using combinatorial and heuristic techniques. 1996-01-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/37 info:doi/10.1016/0305-0548(94)00094-O https://ink.library.smu.edu.sg/context/sis_research/article/1036/viewcontent/cor96.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Numerical Analysis and Scientific Computing Operations Research, Systems Engineering and Industrial Engineering |
| institution |
Singapore Management University |
| building |
SMU Libraries |
| continent |
Asia |
| country |
Singapore Singapore |
| content_provider |
SMU Libraries |
| collection |
InK@SMU |
| language |
English |
| topic |
Numerical Analysis and Scientific Computing Operations Research, Systems Engineering and Industrial Engineering |
| spellingShingle |
Numerical Analysis and Scientific Computing Operations Research, Systems Engineering and Industrial Engineering LAU, Hoong Chuin On the Complexity of Manpower Shift Scheduling |
| description |
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 assignment problem. Our work formally defines the computational intractibility of manpower shift scheduling and thus justifies existing works in developing manpower scheduling systems using combinatorial and heuristic techniques. |
| format |
text |
| author |
LAU, Hoong Chuin |
| author_facet |
LAU, Hoong Chuin |
| author_sort |
LAU, Hoong Chuin |
| title |
On the Complexity of Manpower Shift Scheduling |
| title_short |
On the Complexity of Manpower Shift Scheduling |
| title_full |
On the Complexity of Manpower Shift Scheduling |
| title_fullStr |
On the Complexity of Manpower Shift Scheduling |
| title_full_unstemmed |
On the Complexity of Manpower Shift Scheduling |
| title_sort |
on the complexity of manpower shift scheduling |
| publisher |
Institutional Knowledge at Singapore Management University |
| publishDate |
1996 |
| url |
https://ink.library.smu.edu.sg/sis_research/37 https://ink.library.smu.edu.sg/context/sis_research/article/1036/viewcontent/cor96.pdf |
| _version_ |
1770568862607081472 |