Single operation earliness–tardiness scheduling with machine activation costs
Tóm tắt
We consider a static, single operation, non-pre-emptive, deterministic scheduling problem in which a set of n jobs is to be processed on k identical machines. Jobs assigned to each machine have a common due date. The number of machines (k) is unknown. Activating a machine will require additional costs to be incurred. The objective is to find an optimal sequence, the optimal number of machines (k), and the respective due dates to minimize the weighted sum of earliness, tardiness, and machine activation costs. We propose a polynomial time algorithm to solve the problem.
Tài liệu tham khảo
Adamopoulos, G.I. and Pappis, C.P. (1998) Scheduling under a common due-date on parallel unrelated machines. European Journal of Operational Research, 105, 495–501.
Baker, K.R. and Scudder, G.D. (1990) Sequencing with earliness and tardiness penalties: a review. Operations Research, 38, 22–36.
Biskup, D. and Cheng, T.C.E. (1999) Multiple-machine scheduling with earliness, tardiness and completion time penalties. Computers and Operations Research, 26, 45–57.
Cheng, T.C.E. (1988) Optimal common due date with limited completion time deviation. Computers and Operations Research, 15, 91–96.
Cheng, T.C.E. and Chen, Z.L. (1988) Parallel-machine scheduling problems with earliness and tardiness penalties. Journal of the Operational Research Society, 45, 685–695.
Dey, P., Ghosh, J.B. and Wells, C.E. (1994) Due-date assignment and early/tardy scheduling on identical parallel machines. Naval Research Logistics, 41, 17–32.
Emmons, H.(1987) Scheduling to a common due date on parallel uniform processors. Naval Research Logistics, 34, 803–810.
Hall, N.G. (1986) Scheduling problems with generalized due dates. IIE Transactions, 18, 220–222.
Hall, N.G., Kubiak, W. and Sethi, S.P. (1991) Earliness-tardiness scheduling problems II: deviation of completion times about a restrictive common due date. Operations Research, 39, 847–856.
Hall, N.G. and Posner, M.E. (1991) Earliness-tardiness scheduling problems, I: weighted deviation of completion times about a common due date. Operations Research, 39, 836–846.
Kanet, J.J. (1981) Minimizing the average deviation of job completion times about a common due date. Naval Research Logistics Quarterly, 28, 643–651.
Lee, C.-Y., Liman, S.D. and Lin, C.-S. (1991) Minimizing weighted number of tardy jobs and weighted earliness-tardiness penalties about a common due date. Computers and Operations Research, 18, 379–395.
Liman, S.D. and Lee, C.-Y. (1993) Error bound of a heuristic for the common due date scheduling problem. ORSA Journal on Computing, 5, 420–425.
Panwalkar, S.S., Smith, M.L. and Seidmann, A. (1982) Common due date assignment to minimize total penalty for the one machine scheduling problem. Operations Research, 30, 391–399.
Raghavachari, M.(1988) Scheduling problems with non-regular penalty functions - a review. Opsearch, 25, 144–164.