Single machine scheduling with a variable common due date and resource-dependent processing times

The problem of scheduling n jobs with a variable common due date on a single machine is studied. It is assumed that the job processing times are non-increasing linear functions of an equal amount of a resource allocated to the jobs. The due date and resource values can be continuous or discrete. The objective is to minimize a linear combination of scheduling, due date assignment and resource consumption costs. The resource consumption cost function may be non-monotonous. Algorithms with View the MathML source running times are presented for scheduling costs involving earliness/tardiness and number of tardy jobs. Computational experiments show that the algorithms can solve problems with n=5,000 in less than a minute on a standard PC.