標題: Scheduling step-deteriorating jobs to minimize the total completion time
作者: Cheng, T. C. E.
Kravchenko, Svetlana A.
Lin, Bertrand M. T.
資訊管理與財務金融系
註:原資管所+財金所

Department of Information Management and Finance
關鍵字: Single-machine scheduling;Step deterioration;Total completion time;Ordinary NP-hardness;Dynamic programming
公開日期: 1-六月-2020
摘要: We consider single-machine scheduling to minimize the total completion time, where the processing time of a job is a step function of its start time. In this paper we establish the complexity status of the problem by proving its NP-hardness and developing a dynamic programming algorithm that solves the problem in pseudo-polynomial time.
URI: http://dx.doi.org/10.1016/j.cie.2020.106329
http://hdl.handle.net/11536/154591
ISSN: 0360-8352
DOI: 10.1016/j.cie.2020.106329
期刊: COMPUTERS & INDUSTRIAL ENGINEERING
Volume: 144
起始頁: 0
結束頁: 0
顯示於類別:期刊論文