Minimizing total completion time and total deviation of job completion times from a restrictive due-date |
| |
| Institution: | 2. Department of Radiation Oncology, Qilu Hospital of Shandong University, Jinan, Shandong, China;3. Department of Oncology, The Second People''s Hospital of Dezhou, Shandong, China;4. Cancer Treatment Center, Yantai Affiliated Hospital of Binzhou Medical University, Yantai, Shandong, China;5. Department of Cancer Treatment, The 107th Hospital of the People''s Liberation Army, Yantai, Shandong, China;1. Helmut-Schmidt-Universität, Holstenhofweg 85, 22043 Hamburg, Germany;2. Deutsche Bundesbank – Hannover, Georgsplatz 5, 30159 Hannover, Germany;3. Centre for Applied Macroeconomic Analysis, Australian National University, Canberra, Australia;4. Deutsche Bundesbank, Wilhelm-Epstein-Str. 14, 60431 Frankfurt am Main, Germany;5. Reserve Bank of New Zealand, 2 The Terrace, PO Box 2498, Wellington 6140, New Zealand;1. Czech National Bank, Czech Republic;2. Charles University, Prague, Czech Republic |
| |
| Abstract: | We study a single-machine scheduling problem with the objective of minimizing a linear combination of total job completion times and total deviation of job completion times from a common due-date. The due-date is assumed to be restrictive, i.e., it may be sufficiently small to have an impact on the optimal sequence. When more weight is allocated to total job completion times, the problem is shown to have a polynomial time solution. When more weight is allocated to total completion time deviations from the due-date, the problem is NP-hard in the ordinary sense. For the latter case, we introduce an efficient dynamic programming algorithm, which is shown numerically to perform well in all our tests. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
