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

In this paper a new type of single machine scheduling problem, in whic h 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 we ighted completion times. The general case addressed here is for jobs w ith common pre-duedate processing time, general post-duedate processin g time penalties, and general weights. A switching algorithm is propos ed 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.