Scheduling Jobs with Linear Delay Penalties and Sequence Dependent Setup Costs

We discuss the problem of minimizing the sum of the setup costs and linear delay penalties when N jobs, arriving at time zero, are to be scheduled for sequential processing on a continuously available machine. The delay penalty for each job is a nondecreasing linear function of the sum of the various processing times for preceding jobs. The setup cost for each job is dependent only upon the job that immediately precedes it. The equivalence of the traveling salesman problem to the setup portion of this problem creates a special challenge. The application of several Branch-and-Bound algorithms using various branching rules is discussed. Since the problem has a highly attractive Dynamic Programming formulation, a hybrid algorithm analogous to Morin and Marsten's Dynamic Programming/Branch-and-Bound approach to the traveling salesman problem is also utilized. This technique, detailed in the paper, applies a fathoming criterion to the states of the Dynamic Program in order to drastically reduce memory and computational requirements. We report computational results for a set of randomly generated problems that endorse the effectiveness of one heuristic approach and show the superiority of the hybrid approach over pure Branch-and-Bound methods in yielding confirmed optimal solutions for that set of problems.