×

A hybrid two-stage transportation and batch scheduling problem. (English) Zbl 1167.90520

Summary: We study the coordinated scheduling problem of hybrid batch production on a single batching machine and two-stage transportation connecting the production, where there is a crane available in the first-stage transportation that transports jobs from the warehouse to the machine and there is a vehicle available in the second-stage transportation to deliver jobs from the machine to the customer. As the job to be carried out is big and heavy in the steel industry, it is reasonable assumed that both the crane and the vehicle have unit capacity. The batching machine processes a batch of jobs simultaneously. Each batch occur a setup cost. The objective is to minimize the sum of the makespan and the total setup cost. We prove that this problem is strongly NP-hard. A polynomial time algorithm is proposed for a case where the job transportation times are identical on the crane or the vehicle. An efficient heuristic algorithm for the general problem is constructed and its tight worst-case bound is analyzed. In order to further verify the performance of the proposed heuristics, we develop a lower bound on the optimal objective function. Computational experiments show that the heuristic algorithm performs well on randomly generated problem instances.

MSC:

90B35 Deterministic scheduling theory in operations research
Full Text: DOI

References:

[1] Lee, C.-Y.; Chen, Z.-L., Machine scheduling with transportation considerations, J. Sched., 4, 3-24 (2001) · Zbl 0979.90055
[2] Chang, Y.-C.; Lee, C.-Y., Machine scheduling with job delivery coordination, Eur. J. Oper. Res., 158, 470-487 (2004) · Zbl 1067.90041
[3] Pundoor, G.; Chen, Z.-L., Scheduling a production-distribution system to optimize the tradeoff between delivery tardiness and distribution cost, Nav. Res. Log., 52, 571-589 (2005) · Zbl 1122.90358
[4] Chen, Z.-L.; Vairaktarakis, G. L., Integrated scheduling of production and distribution operations, Manage. Sci., 51, 614-628 (2005) · Zbl 1145.90380
[5] Cheng, T. C.E.; Kahlbacher, H. G., Scheduling with delivery and earliness penalties, Asia-Pac. J. Oper. Res., 10, 145-152 (1993) · Zbl 0789.90041
[6] Cheng, T. C.E.; Gordon, V. S., Batch delivery scheduling on a single machine, J. Oper. Res. Soc., 45, 1211-1215 (1994) · Zbl 0814.90046
[7] Wang, G.; Cheng, T. C.E., Parallel machine scheduling with batch delivery costs, Int. J. Prod. Econ., 68, 177-183 (2000)
[8] Hall, N. G.; Potts, C. N., The coordination of scheduling and batch deliveries, Ann. Oper. Res., 135, 41-64 (2005) · Zbl 1112.90022
[9] Li, C.-L.; Ou, J., Machine scheduling with pickup and delivery, Nav. Res. Log., 52, 617-630 (2005) · Zbl 1151.90422
[10] Potts, C. N.; Kovalyov, M. Y., Scheduling with batching: A review, Eur. J. Oper. Res., 120, 228-249 (2000) · Zbl 0953.90028
[11] Ahmadi, J. H.; Ahmadi, R. H.; Dasu, S.; Tang, C. S., Batching and scheduling jobs on batch and discrete processors, Oper. Res., 39, 750-763 (1992) · Zbl 0758.90042
[12] Sung, C. S.; Kim, Y. H., Minimizing makespan in a two-machine flowshop with dynamic arrivals allowed, Comput. Oper. Res., 29, 275-294 (2002) · Zbl 0993.90051
[13] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman: W.H. Freeman San Francisco · Zbl 0411.68039
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.