Premium
Single machine due‐date scheduling of jobs with decreasing start‐time dependent processing times
Author(s) -
Cheng T. C. E.,
Kang L. Y.,
Ng C. T.
Publication year - 2005
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2005.501_1.x
Subject(s) - tardiness , single machine scheduling , due date , scheduling (production processes) , computer science , mathematical optimization , schedule , job shop scheduling , mathematics , operating system
We study the problem of scheduling jobs whose processing times are decreasing functions of their starting times. We consider the case of a single machine and a common decreasing rate for the processing times. The problem is to determine an optimal combination of the due date and schedule so as to minimize the sum of due date, earliness and tardiness penalties. We give an O ( n log n ) time algorithm to solve this problem.