The Single Machine Problem with Quadratic Penalty Function of Completion Times: A Branch-and-Bound Solution

Abstract

N jobs are to be sequenced on a single machine, each job carrying a penalty cost which is a quadratic function of its completion time. The objective is to find a sequence which minimizes the total penalty. Criteria are developed for ordering a pair of adjacent jobs in a sequence and these are incorporated into a branch-and-bound procedure.