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

Wlodzimierz Szwarc, Marc E. Posner and John J. Liu
Additional contact information
Wlodzimierz Szwarc: School of Business Administration, University of Wisconsin, Milwaukee, Wisconsin 53201
Marc E. Posner: Industrial and Systems Engineering Department, Ohio State University, Columbus, Ohio 43210
John J. Liu: School of Business Administration, University of Wisconsin, Milwaukee, Wisconsin 53201

Management Science, 1988, vol. 34, issue 12, 1480-1488

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 (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.34.12.1480 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:34:y:1988:i:12:p:1480-1488

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().