A Problem in Single-Machine Sequencing with Nonlinear Delay Costs

We examine a class of single-machine sequencing problems which originate from scheduling considerations for a single-server queueing system with nonlinear costs of delay. Associated with each request awaiting service (sequencing) are a known service time, a known arrival time, and a nondecreasing cost function which is identical for each request. Two sequencing problems are considered; a request incurs cost from its arrival time to the time when it (1) commences service or (2) completes service. Our objective is a sequence which minimizes the total incurred cost.

Necessary conditions for the optimal sequencing of requests are given for convex nondecreasing and quadratic cost functions. These conditions and a new lower bound function are used in a branch-and-bound algorithm to obtain computational results.