The single machine problem with a quadratic cost function of completion times

The single machine problem with a quadratic cost function of completion times

0.00 Avg rating0 Votes
Article ID: iaor1988112
Country: United States
Volume: 34
Issue: 12
Start Page Number: 1480
End Page Number: 1488
Publication Date: Dec 1988
Journal: Management Science
Authors: , ,
Keywords: programming: quadratic
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.