Single machine scheduling subject to deadlines and resource dependent processing times |
| |
| Institution: | 1. ABB Corporate Research Germany, Wallstadter Str. 59, Ladenburg 68526, Germany;1. Dipartimento di Informatica, Università di Pisa, Largo B. Pontecorvo 3, Pisa 56127, Italy;2. DEI “Guglielmo Marconi”, Università di Bologna, Viale Risorgimento 2, Bologna 40136, Italy;1. Centro de Matemática Aplicações Fundamentais e Investigação Operacional, Faculdade de Ciências, Universidade de Lisboa, Lisboa, 1749-016, Portugal;2. ABB Corporate Research, Wallstadter Strasse 59, Ladenburg, 68526, Baden-Württemberg, Germany;3. Center for Advanced Process Decision-Making, Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA 15213, USA;1. School of Science, Nanjing University of Science and Technology, Nanjing, Jiangsu 210094, People’s Republic of China;2. School of Automobile and Traffic Engineering, Jiangsu University of Technology, Changzhou, Jiangsu, 213001, People’s Republic of China;1. Department of Industrial Management, National Taiwan University of Science and Technology, Taipei, Taiwan;2. Artificial Intelligence for Operations Management Research Center, National Taiwan University of Science and Technology, Taipei, Taiwan;3. School of Mathematical and Physical Sciences, University of Technology Sydney, Sydney, Australia |
| |
| Abstract: | The problem of scheduling n jobs on a single machine is studied. Each job has a deadline and a processing time which is a linear decreasing function of the amount of a common resource allocated to the job. The objective is to find simultaneously a sequence of the jobs and a resource allocation so as the deadlines are satisfied and the total weighted resource consumption is minimized. The problem is shown to be solvable in O(n log n) time if the resource is continuously divisible. If the resource is discrete, then the problem is proved to be binary NP-hard. Some special cases are solvable in O(n log n) time. A fully polynomial approximation scheme is presented for the general problem with discrete resource. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
