The Single Machine Problem with a Quadratic Cost Function of Completion Times
Wlodzimierz Szwarc, Marc E. Posner, John J. Liu
Management Science · 1988 · Volume 34 · Issue 12
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.
Keywords
product/scheduling, programming: deterministic, discrete time, programming: quadratic
Enable JavaScript for citation tools and additional paper interactions.