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.

• 저널Management Science · 22(12) · 1342–1350
• 토픽Scheduling and Optimization Algorithms · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.22.12.1342
• 저자Peter Henderson, Kenneth Steiglitz