Optimal Sequencing of a Single Machine Subject to Precedence Constraints

Suppose n jobs are each to be processed by a single machine, subject to arbitrary given precedence constraints. Associated with each job j is a known processing time a j , and a monotone nondecreasing cost function c j (t), giving the cost that is incurred by the completion of that job at time t. The problem is to find a sequence which will minimize the maximum of the incurred costs. An efficient computational procedure is given for this problem, generalizing and simplifying previous results of the present author and J. M. Moore.

• 저널Management Science · 19(5) · 544–546
• 토픽Scheduling and Optimization Algorithms · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.19.5.544
• 저자Eugene L. Lawler