| 具有正比权值完工时间与交货期偏差加权和最小化单机随机调度 |
| |
| 引用本文： | 贾春福.具有正比权值完工时间与交货期偏差加权和最小化单机随机调度[J].南开大学学报,2003,36(2):93-97. |
| |
| 作者姓名： | 贾春福 |
| |
| 作者单位： | 南开大学信息技术科学学院，天津300071 |
| |
| 基金项目： | Partially Supported by Tianjin Natural Science Foundation of China(0 1 3 60 0 71 1 )，Supported by National Climbing Projectof China (970 2 1 1 0 1 7) |
| |
| 摘 要： | 完工时间与交货期偏差加权和最小化单机调度(简记TWD)问题是Just—In—Time生产环境下典型的调度模型，是NP—hard问题．然而工件权值与加工时间成正比时，LPT(Largest Processing Time)调度最优．本考虑了随机TWD问题，其中工件的加工时间和交货期都服从指数分布，证明了LEPT(Largest Expected Processing Time)调度的最优性，并进一步将结论推广到机器随机故障的情形．
|
| 关 键 词： | 随机单机调度 随机加工时间 随机交货期 正比权值 |
STOCHASTIC SINGLE MACHINE SCHEDULING TO MINIMIZE TOTAL WEIGHTED DEVIATIONS OF COMPLETION TIMES FROM A COMMON DUE DATE WITH PROPORTIONAL WEIGHTS |
| |
| Abstract.STOCHASTIC SINGLE MACHINE SCHEDULING TO MINIMIZE TOTAL WEIGHTED DEVIATIONS OF COMPLETION TIMES FROM A COMMON DUE DATE WITH PROPORTIONAL WEIGHTS[J].Acta Scientiarum Naturalium University Nankaiensis,2003,36(2):93-97. |
| |
| Authors: | Abstract |
| |
| Abstract: | The deterministic problem of minimizing total weighted deviations of job completion times from a common due date on a single machine (abbreviated to TWD problem) is a typical scheduling model in Just-In-Time production environment. The general TWD problem is NP-hard. However, the LPT (Largest Processing Time) job sequence is optimal for the case where the job weights are proportional to processing times. In this paper, we consider the stochastic counterpart of the TWD problem with proportional weights. The processing times and the due date are exponentially distributed random variables with arbitrary positive rates. It is shown that the LEPT (Largest Expected Processing Time) job sequence is optimal. Moreover, the case where the machine is subject to stochastic breakdowns is also discussed. |
| |
| Keywords: | stochastic scheduling single machine scheduling random processing times random due date proportional weight |
| 本文献已被 CNKI 维普 等数据库收录！ |
