Minimizing the sum of weighted completion times of n-independent jobs when resource availability varies over time: Performance of a simple priority rule. (English) Zbl 0631.90032
Our objective is to evaluate the performance of a WSPT (weighted shortest processing time) rule for scheduling n independent jobs where the resources to process these jobs vary over time and a job can be processed by several processors simultaneously. This problem was raised by K. R. Baker and H. L. W. Nuttle [Nav. Res. Logist. Q. 27, 499-510 (1980; Zbl 0446.90043)]. A linear-programming (LP) model is formulated to obtain a lower bound on the minimum value of the weighted completion times. The purpose of the model is to provide a basis for evaluating the WSPT heuristic. 1000 experiments were performed using different resource profiles to test the performance of WSPT. Using WSPT, the weighted completion times were found to be, on the average, 0.2% away from their LP lower bounds.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 65K05 | Numerical mathematical programming methods |
| 90C05 | Linear programming |
Keywords:
weighted shortest processing timeCitations:
Zbl 0446.90043Software:
LINDOReferences:
| [1] | Introduction to Sequencing and Scheduling, Wiley, New York, 1974. |
| [2] | Baker, Naval Research Logistics Quarterly 27 pp 499– (1980) |
| [3] | , and , Theory of Scheduling, Addison-Wesley, Reading, MA, 1967. |
| [4] | User’s Manual for LINDO, The Scientific Press, Palo Alto, CA, 1981. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
