Generalized preemption models for single-machine dynamic scheduling problems
Tóm tắt
In the extensive scheduling literature, job preemption, if allowed, implies that the processing of a partly completed job is temporarily halted and later resumed at the same point. However, little attention has been given to problems where job preemption is allowed under the condition that either some startup time delay must be incurred or some fraction of work must be repeated if preemption occurs. We generalize the notion of job preemption by using models representing these conditions. The models are applied to studying the dynamic single-machine scheduling problems of minimizing total flow time, and of minimizing maximum lateness, subject to arbitrary and unknown job ready dates. On-line optimal dispatching rules, which consider only available – as opposed to look-ahead – information, are developed. These rules determine, on arrival or completion of each job, which available job should next be processed by the machine. A special case of our models, the preempt-repeat scenario, where preempted jobs must be totally repeated, is suggested as heuristic for the equivalent non-preemptive static problem where all ready dates are known and given. A computational study is performed to determine the potential benefits of reducing startup time delays or work repetition fractions in the context of continuous improvement of manufacturing systems.
Tài liệu tham khảo
Baker, K.R. (1974) Introduction to Sequencing and Scheduling, John Wiley and Sons.
Lenstra, J.K., Rinnooy Kan, A.H.G. and Brucker, P. (1977) Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 75–90.
Smith, W.E. (1956) Various optimizers for single-state production. Naval Research Logistics Quarterly, 3(1), 59–66.
Jackson, J.K. (1955) Scheduling a production line to minimize maximum tardiness. Research Report 43, Management Science Research Project, University of California, Los Angeles.
Bianco, L. and Ricciardelli, S. (1982) Scheduling of a single machine to minimize total weighted completion time subject to release dates. Naval Research Logistics Quarterly, 29(1), 151–167.
Chandra, R. (1979) On n/1/{ie372-01} dynamic deterministic problems. Naval Research Logistics Quarterly 26, 537–544.
Deogun, J.S. (1983) On scheduling with ready times to minimize mean flow time. Computing Journal, 26(4), 320–338.
Dessouky, M.I. and Deogun, J.S. (1981) Sequencing jobs with unequal ready times to minimize mean flow time. SIAM Journal of Computing, 10(1), 192–202.
Hariri, A.M.A. and Potts, C.N. (1983) An algorithm for single machine sequencing with release dates to minimize total weighted completion time. Discrete Applied Mathematics, 5, 99–109.
Beshara, S.B. and Magazine, M.J. (1981) Myopic heuristics for single machine scheduling problems. International Journal of Production Research, 19(1), 85–95.
Posner, M.E. (1986) A sequencing problem with release dates and clustered jobs. Management Science, 32(6), 731–738.
Conway, R.W., Maxwell, W.L. and Miller, L.W. (1967) Theory of Scheduling, Addison-Wesley, Reading, MA.
Porteus, E.L. (1985) Investing in reduced setups in the EOQ model. Management Science, 31(8), 998–1010.
Porteus, E.L. (1986) Optimal lot sizing: process quality improvement and setup cost reduction. Operations Research, 34(1), 137–144.
Du, J. and Leung, J.Y.-T. (1990) Minimizing total tardiness on one machine is NP-hard Mathematics of Operations Research, 15, 483–495.