Note: “Simultaneous optimization of efficiency and performance balance measures in single-machine scheduling problems”
✍ Scribed by Michael X. Weng; Jose A. Ventura
- Publisher
- John Wiley and Sons
- Year
- 1996
- Tongue
- English
- Weight
- 280 KB
- Volume
- 43
- Category
- Article
- ISSN
- 0894-069X
No coin nor oath required. For personal study only.
✦ Synopsis
n independent jobs are to be scheduled nonpreemptively on a single machine so as to minimize some performance measure. Federgruen and Mosheiov [ 21 show that a large class of such scheduling problems can be optimized by solving either a single instance or a finite sequence of instances of the so-called SQC problem, in which all the jobs have a fixed or controllable common due date and the sum of general quasiconvex functions of the job completion times is to be minimized. In this note we point out that this is not always true. In particular, we show that the algorithm proposed in [2] does not always find a global optimal schedule to the problem of minimizing the weighted sum of the mean and variance ofjob completion times. 0 1996 John Wiley & Sons, Inc.
INTRODUCIION
Many manufacturing companies aim to achieve just-in-time (JIT) production. Inman and Bulfin [ 41 show that this problem may be interpreted as a single-machine scheduling problem with the objective of minimizing a function of the earliness and tardiness over all jobs. A variety of algorithms have been developed to solve this class of problems (interested readers are referred to Baker and Scudder [ 1 ] for an extensive review). Federgruen and Mosheiov [2] show that a large class of such scheduling problems can be optimized by solving either a single instance or a finite sequence of instances of the so-called SQC problem, in which all the jobs have a fixed or controllable common due date and the sum of general quasiconvex functions of the job completion times is to be minimized.
The purpose of this note is to point out through some examples that this is not always true. In particular, we show that the algorithm proposed in [ 21 does not guarantee finding a global optimal schedule for the problem of simultaneously minimizing the mean and variance of job completion times.
1. MODEL
Consider n independent jobs to be processed nonpreemptively on a single machine. Assume that each job has release time equal to zero. Given job i , let pi be its integer-valued