|
|||||
|
|
A polynomial time algorithm for a chance-constrained single machine scheduling problem |
|
| Authors: | Naoki Katoh Toshihide Ibaraki |
| Affiliation: | Department of Management Science, Kobe University of Commerce, Tarumi, Kobe, Japan 655;Department of Information and Computer Sciences, Toyohashi University of Technology, Tempaku-Cho, Toyohashi, Japan 440 |
| Abstract: | This paper gives an O(n√nlog3n) time algorithm for the chance-constrained sequencing problem on a single machine, where n is the number of jobs and the objective is to minimize the number of jobs which are early with probability not smaller than α (a given constant) against the common due time d. |
| Keywords: | Chance-constrained sequencing problem single machine scheduling polynomial time algorithm NP-hardness |
| 本文献已被 ScienceDirect 等数据库收录！ | |