.png){kind=icon}
Return
LICENSE CLASS DESIGN - COMPLEXITY AND ALGORITHMS
.png){kind=icon}
OA
AI
DOI：10.1016/0377-2217(92)90160-B.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper a generalization of the Fixed Job Scheduling Problem (FSP) is considered, which appears in the aircraft maintenance process at an airport. A number of jobs have to be carried out, where the main attributes of a job are a fixed start time, a fixed finish time and an aircraft type. For carrying out these jobs a number of engineers are available. An engineer is allowed to carry out a specific job only if he has a license for the corresponding aircraft type. Furthermore, the jobs must be carried out in a non-preemptive way and each engineer can be carrying out at most one job at the same time. Within this setting natural questions to be answered ask for the minimum number of engineers required for carrying out all jobs or, more generally, for the minimum total costs for hiring engineers. In this paper a complete classification of the computational complexity of two classes of mathematical problems related to these practical questions is given. Furthermore, it is shown that the polynomially solvable cases of these problems can be solved by a combination of Linear Programming and Network Flow algorithms.
Keywords:
CAPACITY PLANNING
COMPUTATIONAL COMPLEXITY
FIXED JOB INTERVALS
JOB SCHEDULING
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
Organization
No organization information available
Cited Papers
.png){kind=icon}
ShareSave
ShareSaveShareSave no more
no more