Scheduling Multiple Variable-Speed Machines

Michael A. Trick
Additional contact information
Michael A. Trick: Carnegie Mellon University, Pittsburgh, Pennsylvania

Operations Research, 1994, vol. 42, issue 2, 234-248

Abstract: We examine scheduling problems where we control not only the assignment of jobs to machines, but also the time used by the job on the machine. For instance, many tooling machines allow control of the speed at which a job is run. Increasing the speed incurs costs due to machine wear, but also increases throughput. We discuss some fundamental scheduling problems in this environment and give algorithms for some interesting cases. Some cases are inherently difficult so for these we give heuristics. Our approach illustrates the exploitation of underlying network structure in combinatorial optimization problems. We create heuristics that optimally schedule a large portion of the jobs and then attempt to fit in the remainder. This also gives a method for quickly finding valid inequalities violated by the linear relaxation solution. For the problem of minimizing the sum of makespan and production costs, a rounding heuristic is within a constant factor of optimal. Our heuristics are compared to other classical heuristics.

Keywords: networks/graphs; heuristics: heuristics for scheduling machines; production/scheduling; open shop; single stage: variable speed machines (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.2.234 (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:oropre:v:42:y:1994:i:2:p:234-248

Access Statistics for this article

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