Single-Machine Time-Dependent Scheduling with Proportional and Delivery Times
Abstract
We consider the time-dependent scheduling with proportional and delivery times on a single machine. Three models of the processing times are addressed here, they are proportional deterioration, proportional-linear shortening and proportional-linear increasing. The objective is to minimize the time by which all jobs are delivered. For the first model, we prove that the problem is polynomial solvable when jobs have identical release dates. When jobs arrive dynamically, we first give the proof of the NP-hardness and present a two-approximation algorithm. Then we propose a fully polynomial time approximation scheme for the case where the number of distinct release dates is a constant by applying the “rounding-the-input-data” technique. For the second and third models, when jobs have identical release dates, we prove that they are polynomial solvable, when jobs have different release dates, we present two-approximation algorithms for each of them.
