SCHEDULING MULTIPLE VARIABLE-SPEED MACHINES
成果类型：
Article
署名作者：
TRICK, MA
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.42.2.234
发表日期：
1994
页码：
234-248
关键词：
摘要：
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.