| Affiliation: | a Adam Mickiewicz University, Faculty of Mathematics and Computer Science, Umultowska 87, 61-614 Poznań, Poland
b Department of Information and Finance Management, Institute of Information Management, National Chiao Tung University, 1001 Ta Hsueh Road, Hsinchu 300, Taiwan |
| Abstract: | We consider a new model of time-dependent scheduling. A set of deteriorating jobs has to be processed on a single machine which is available starting from a non-zero time. The processing times of some jobs from this set are constant, while other ones are either proportional or linear functions of the job starting times. The applied criteria of schedule optimality include the maximum completion time, the total completion time, the total weighted completion time, the maximum lateness and the number of tardy jobs. We delineate a sharp boundary between computationally easy and difficult problems, showing polynomially solvable and NP-hard cases. |
