| Title: | Scheduling step-deteriorating jobs to minimize the total completion time |
| Authors: | Cheng, T. C. E. Kravchenko, Svetlana A. Lin, Bertrand M. T. 資訊管理與財務金融系 註：原資管所+財金所 Department of Information Management and Finance |
| Keywords: | Single-machine scheduling;Step deterioration;Total completion time;Ordinary NP-hardness;Dynamic programming |
| Issue Date: | 1-Jun-2020 |
| Abstract: | 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 |
| Journal: | COMPUTERS & INDUSTRIAL ENGINEERING |
| Volume: | 144 |
| Begin Page: | 0 |
| End Page: | 0 |
| Appears in Collections: | Articles |
- Scheduling time-dependent jobs under mixed deterioration / Gawiejnowicz, Stanislaw;Lin, Bertrand M. T.
- Relocation scheduling subject to fixed processing sequences / Lin, Bertrand M. T.;Hwang, F. J.;Kononov, Alexander V.
- Scheduling with Centralized and Decentralized Batching Policies in Concurrent Open Shops / Lin, B. M. T.;Cheng, T. C. E.
- A note on parallel-machine scheduling with deteriorating jobs / Jeng, A. A. K.;Lin, B. M. T.
- Scheduling of a two-stage differentiation flowshop to minimize weighted sum of machine completion times / Cheng, T. C. E.;Lin, B. M. T.;Tian, Y.
- 平行流線型機組排程-總完工時間之最小化 / 林延聰;Y.T. Lin;林妙聰;B.M.T. Lin
- Total completion time minimization in two-machine flow shop scheduling problems with a fixed job sequence / Hwang, F. J.;Kovalyov, M. Y.;Lin, B. M. T.
Loading...