Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs

Abstract

A one-machine deterministic job-shop sequencing problem is considered. Associated with each job is its processing time and linear deferral cost. In addition, the jobs are related by a general precedence relation. The objective is to order the jobs so as to minimize the sum of the deferral costs, subject to the constraint that the ordering must be consistent with the precedence relation. A decomposition algorithm is presented, and it is proved that a permutation is optimal if and only if it can be generated by this algorithm. Four special network structures are then considered, and specializations of the general algorithm are presented.