Preemptive scheduling in a two-stage supply chain to minimize the makespan. (English) Zbl 1335.90040
Summary: This paper deals with the problem of preemptive scheduling in a two-stage supply chain framework. The supply chain environment contains two stages: production and transportation. In the production stage \(n\) jobs are processed on a manufacturer’s bounded serial batching machine, preemptions are allowed, and set-up time is required before a new batch is processed. In the transportation stage each batch is delivered to a customer by a single vehicle. The objective is to minimize the makespan by making decisions for both mutually coordinated stages. Specifically, two versions are studied. The first one is that all jobs are available to be processed at time zero, and the second one is that jobs have different release times. An \(O(n\log n)\) time algorithm is developed for the first version, and we show that it can produce the optimal schedule for the entire problem. For the second version, based on some useful properties we have designed an \(O(n\log n)\) time heuristic and a novel lower bound. The worst-case performance ratio of our algorithm is bounded by \(2\). Our computational study with random instances of different scales shows high-quality solutions for either small-scale or large-scale instances returned in a reasonable PC times.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C11 | Mixed integer programming |
| 90B06 | Transportation, logistics and supply chain management |
References:
| [1] | DOI: 10.1016/j.cie.2009.01.010 · doi:10.1016/j.cie.2009.01.010 |
| [2] | DOI: 10.1016/j.ejor.2006.09.010 · Zbl 1137.90475 · doi:10.1016/j.ejor.2006.09.010 |
| [3] | DOI: 10.1016/j.ejor.2006.06.004 · Zbl 1121.90051 · doi:10.1016/j.ejor.2006.06.004 |
| [4] | Bard J.F., Comput. Ind. Eng 37 (12) pp 2202– (2010) |
| [5] | DOI: 10.1080/10556788.2013.854360 · Zbl 1299.90131 · doi:10.1080/10556788.2013.854360 |
| [6] | DOI: 10.1016/S0167-6377(02)00220-1 · Zbl 1041.90015 · doi:10.1016/S0167-6377(02)00220-1 |
| [7] | DOI: 10.1080/00207543.2011.578162 · doi:10.1080/00207543.2011.578162 |
| [8] | DOI: 10.1016/j.cor.2012.08.017 · Zbl 1349.90331 · doi:10.1016/j.cor.2012.08.017 |
| [9] | DOI: 10.1007/s00170-008-1653-8 · doi:10.1007/s00170-008-1653-8 |
| [10] | DOI: 10.1016/j.eswa.2010.05.060 · doi:10.1016/j.eswa.2010.05.060 |
| [11] | Geunes J., Supply Chain Optimization (2003) |
| [12] | DOI: 10.1016/j.ejor.2008.07.044 · Zbl 1163.90781 · doi:10.1016/j.ejor.2008.07.044 |
| [13] | DOI: 10.1016/S0167-5060(08)70356-X · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |
| [14] | DOI: 10.1287/opre.51.4.566.16106 · Zbl 1165.90455 · doi:10.1287/opre.51.4.566.16106 |
| [15] | DOI: 10.1109/MC.2002.999778 · doi:10.1109/MC.2002.999778 |
| [16] | DOI: 10.1016/j.ijpe.2012.05.002 · doi:10.1016/j.ijpe.2012.05.002 |
| [17] | DOI: 10.1016/j.disopt.2009.05.005 · Zbl 1175.90180 · doi:10.1016/j.disopt.2009.05.005 |
| [18] | DOI: 10.1016/j.cor.2006.07.006 · Zbl 1180.90131 · doi:10.1016/j.cor.2006.07.006 |
| [19] | DOI: 10.1016/j.apm.2010.07.023 · Zbl 1202.90140 · doi:10.1016/j.apm.2010.07.023 |
| [20] | DOI: 10.1016/j.ijpe.2011.11.011 · doi:10.1016/j.ijpe.2011.11.011 |
| [21] | DOI: 10.1016/j.tcs.2010.05.032 · Zbl 1207.68112 · doi:10.1016/j.tcs.2010.05.032 |
| [22] | DOI: 10.1007/s10589-008-9206-5 · Zbl 1202.90143 · doi:10.1007/s10589-008-9206-5 |
| [23] | DOI: 10.1016/j.ijpe.2009.01.007 · doi:10.1016/j.ijpe.2009.01.007 |
| [24] | DOI: 10.1080/00207543.2010.528461 · doi:10.1080/00207543.2010.528461 |
| [25] | DOI: 10.1016/j.tcs.2009.02.019 · Zbl 1172.90005 · doi:10.1016/j.tcs.2009.02.019 |
| [26] | DOI: 10.1016/j.amc.2012.04.066 · Zbl 1278.90054 · doi:10.1016/j.amc.2012.04.066 |
| [27] | DOI: 10.1016/j.cie.2009.06.012 · doi:10.1016/j.cie.2009.06.012 |
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.
