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: | Szwarc Wlodzimierz, Posner Marc E., Liu John J. |
Keywords: | programming: quadratic |
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.