×

Machine scheduling with job delivery coordination. (English) Zbl 1067.90041

Summary: This paper considers together machine scheduling and finished product delivery. In particular, it addresses the situation in which jobs require different amounts of storage space during delivery. Three scenarios of the problem are discussed. For the problem in which jobs are processed on a single machine and delivered by a single vehicle to one customer area, we provide a proof of NP-hardness and a heuristic with worst-case analysis. The worst-case performance ratio for our heuristic is proven to be 5/3, and the bound is tight. For the problem in which jobs are processed by either one of two parallel machines and delivered by a single vehicle to one customer area, our heuristic could cause at most 100% error under the worst-case with the bound being tight. For the problem that considers jobs to be processed by a single machine and delivered by a single vehicle to two customer areas, we provide another heuristic that is 100% error bound.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Ahmadi, J.H.; Ahmadi, R.H.; Dasu, S.; Tang, C.S., Batching and scheduling jobs on batch and discrete processors, Operations research, 39, 750-763, (1992) · Zbl 0758.90042
[2] Bramel, J.; Simchi-Levi, D., The logic of logistics, (1997), Springer New York · Zbl 0931.90002
[3] Chen, Z.-L., Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs, European journal of operational research, 93, 49-60, (1996) · Zbl 0916.90147
[4] Cheng, T.C.E.; Gordon, V.S.; Kovalyov, M.Y., Single machine scheduling with batch deliveries, European journal of operational research, 94, 277-283, (1996) · Zbl 0947.90579
[5] Ganesharajah, T.; Hall, N.G.; Sriskandarajah, C., Design and operational issues in AGV-served manufacturing systems, Annals of operations research, 76, 109-154, (1998) · Zbl 0896.90083
[6] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[7] Gemmill, D.D.; Stevens, J.W., Scheduling a two-machine flowshop with travel times to minimize maximum lateness, International journal of production research, 35, 1-15, (1997) · Zbl 0940.90509
[8] Graham, R.L.; Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of discrete mathematics, 5, 287-326, (1979) · Zbl 0411.90044
[9] Hall, L.A.; Shmoys, B., Jackson’s rule for single-machine scheduling: making a good heuristic better, Mathematics of operations research, 17, 22-35, (1992) · Zbl 0781.90052
[10] Hall, N.G., Potts, C.N., 2000. Supply chain scheduling: Batching and delivery. Working Paper, Department of Management Sciences, The Ohio State University, Columbus, OH
[11] Hall, N.G.; Lesaoana, M.A.; Potts, C.N., Scheduling with fixed delivery dates, Operations research, 49, 134-144, (2001) · Zbl 1163.90459
[12] Herrmann, J.W.; Lee, C.-Y., On scheduling to minimize earliness-tardiness and batch delivery costs with a common due date, European journal of operational research, 70, 272-288, (1993) · Zbl 0842.90060
[13] Hurink, J.; Knust, S., Makespan minimization for flow-shop problems with transportation times, Discrete applied mathematics, 112, 199-216, (2001) · Zbl 0990.90041
[14] Johnson, S.M., Optimal two- and three-stage production schedules with setup times included, Naval research logistics quarterly, 1, 61-68, (1954) · Zbl 1349.90359
[15] Kise, H., On an automated two-machine flowshop scheduling problem with infinite buffer, Journal of the operations research society of Japan, 34, 354-361, (1991) · Zbl 0747.90048
[16] Lee, C.-Y.; Chen, Z.-L., Machine scheduling with transportation considerations, Journal of scheduling, 4, 3-24, (2001) · Zbl 0979.90055
[17] Maggu, P.L.; Das, G., On 2×n sequencing problem with transportation times of jobs, Pure and applied mathematika science, 12, 1-6, (1980) · Zbl 0441.90039
[18] Maggu, P.L.; Das, G.; Kumar, R., On equivalent job-for-job block in 2×n sequencing problem with transportation times, Journal of the operations research society of Japan, 24, 136-146, (1981) · Zbl 0459.90033
[19] Panwalkar, S.S., Scheduling of a two-machine flowshop with travel time between machines, Journal of the operational research society, 42, 609-613, (1991) · Zbl 0727.90037
[20] Potts, C.N., Analysis of a heuristic for one machine sequencing with release dates and delivery times, Operations research, 28, 1436-1441, (1980) · Zbl 0447.90041
[21] Potts, C.N.; Kovalyov, M.Y., Scheduling with batching: A review, European journal of operational research, 120, 228-249, (2000) · Zbl 0953.90028
[22] Potts, C.N.; Van Wassenhove, L.N., Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity, Journal of the operational research society, 43, 395-406, (1992) · Zbl 0756.90050
[23] Simchi-Levi, D., New worst case results for the bin-packing problem, Naval research logistics, 41, 579-585, (1994) · Zbl 0809.90111
[24] Stern, H.I.; Vitner, G., Scheduling parts in a combined production-transportation work cell, Journal of the operational research society, 41, 625-632, (1990) · Zbl 0703.90047
[25] Webster, S.; Baker, K.R., Scheduling groups of jobs on a single machine, Operations research, 43, 692-703, (1995) · Zbl 0857.90062
[26] Woeginger, G.J., Heuristics for parallel machine scheduling with delivery times, Acta informatica, 31, 503-512, (1994) · Zbl 0818.68040
[27] Yang, X., Scheduling with generalized batch delivery dates and earliness penalties, IIE transactions, 32, 735-741, (2000)
[28] Yuan, J., A note on the complexity of single-machine scheduling with a common due date, earliness – tardiness, and batch delivery costs, European journal of operational research, 94, 203-205, (1996) · Zbl 0929.90041
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.