SINGLE-MACHINE SCHEDULING WITH START TIME-DEPENDENT PROCESSING TIMES - SOME SOLVABLE CASES

In this paper a new type of single machine scheduling problem, in which the processing time is a binary function of a common start time due date is defined. The jobs have processing time penalties for starting after the due date, and the objective is to minimize the sum of the weighted completion times. The general case addressed here is for jobs with common pre-duedate processing time, general post-duedate processing time penalties, and general weights. A switching algorithm is proposed for this case and we conjecture that it is optimal. A 0-1 quadratic programming formulation of this problem is presented. Solvable cases, one with two different weights, another with two different penalties and another with structured weights and penalties have been identified and polynomial time optimal algorithms have been proposed for them.