The Single Machine Problem with a Quadratic Cost Function of Completion Times

This paper examines a single machine sequencing problem with a quadratic cost function of completion times. A new type of precedence relation is constructed that determines the ordering between adjacent jobs. Each pair of jobs has a critical start time, after which the precedence relation changes direction. These relations are incorporated into a solution procedure that solved 191 out of 200 test problems with job sizes ranging from 15 to 100 without using enumeration methods. Although 9 problems were not solved directly by the procedure, even these were reduced to 10 much smaller problems (of the job sizes 3 and 4) which could easily be solved by inspection.

• 저널Management Science · 34(12) · 1480–1488
• 토픽Scheduling and Optimization Algorithms · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.34.12.1480
• 저자Włodzimierz Szwarc, Marc E. Posner, John J. Liu