Two-agent supply chain scheduling problem to minimize the sum of the total weighted completion time and batch cost. (English) Zbl 1384.90050
Summary: Two-agent single-machine scheduling problem is considered in this paper. Agent \(A\)’s goal is to minimize the sum of the total weighted delivery time and the total delivery cost, and agent \(B\) has the delivery time window. First, the NP-hardness of the general problem is proved, and then two special cases are considered. One case is that \(A\)’s jobs have agreeable ratio and this problem is still NP-hard. A pseudo-polynomial dynamic programming algorithm and a \(\frac{3}{2}\)-approximation algorithm are designed. In the other case, \(A\)’s jobs have agreeable ratio and \(B\)’s jobs have deadline at the same time. This problem is polynomial solvable.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Baker, K.R., Smith, J.C.: A multiple-criterion model for machine scheduling. J. Sched. 6(1), 7-16 (2003) · Zbl 1154.90406 · doi:10.1023/A:1022231419049 |
| [2] | Agnetis, A., Billaut, J.C., Gawiejnowicz, S., Pacciarelli, D., Soukhal, A.: Scheduling problems with two competing agents. Oper. Res. 52(2), 229-242 (2004) · Zbl 1165.90446 · doi:10.1287/opre.1030.0092 |
| [3] | Pacifici, A., Agnetis, A., Pacciarelli, D.: Multi-agent Scheduling: Models and Algorithms. Springer, Berlin (2014) · Zbl 1144.90375 |
| [4] | Perez-Gonzalez, P., Framinan, J.M.: A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: multi-agent scheduling problems. Eur. J. Oper. Res. 235(1), 1-16 (2014) · Zbl 1305.90196 · doi:10.1016/j.ejor.2013.09.017 |
| [5] | Orona, D., Shabtayb, D., Steiner, G.: Single machine scheduling with two competing agents and equal job processing times. Eur. J. Oper. Res. 244(1), 86-99 (2015) · Zbl 1346.90378 · doi:10.1016/j.ejor.2015.01.003 |
| [6] | Elvikis, D., T’Kindt, V.: Two-agent scheduling on uniform parallel machines with min-max criteria. Ann. Oper. Res. 213(1), 79-94 (2014) · Zbl 1296.90043 · doi:10.1007/s10479-012-1099-0 |
| [7] | Ng, C.T., Yuan, J.J., Cheng, T.C.E.: Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theor. Comput. Sci. 362(1-3), 273-281 (2006) · Zbl 1100.68007 |
| [8] | Cheng, T.C.E., Ng, C.T., Yuan, J.J.: Multi-agent scheduling on a single machine with max-form criteria. Eur. J. Oper. Res. 188(2), 603-609 (2008) · Zbl 1129.90023 · doi:10.1016/j.ejor.2007.04.040 |
| [9] | Lee, C.Y., Chen, Z.L.: Machine scheduling with transportation considerations. J. Sched. 4(1), 3-24 (2001) · Zbl 0979.90055 · doi:10.1002/1099-1425(200101/02)4:1<3::AID-JOS57>3.0.CO;2-D |
| [10] | Ji, M., He, Y., Cheng, T.C.E.: Batch delivery scheduling with batch delivery cost on a single machine. Eur. J. Oper. Res. 176(2), 745-755 (2007) · Zbl 1125.90018 · doi:10.1016/j.ejor.2005.09.006 |
| [11] | Chen, Z.L., Vairaktarakis, G.L.: Integrated scheduling of production and distribution operations. Manag. Sci. 51(4), 614-628 (2005) · Zbl 1145.90380 · doi:10.1287/mnsc.1040.0325 |
| [12] | Hall, N.G., Potts, C.N.: The coordination of scheduling and batch deliveries. Ann. Oper. Res. 135, 41-64 (2005) · Zbl 1112.90022 · doi:10.1007/s10479-005-6234-8 |
| [13] | Dawande, M., Geismar, H.N., Hall, N.G., Sriskandarajah, C.: Supply chain scheduling: distribution systems. Prod. Oper. Manag. 15(2), 243-261 (2006) · doi:10.1111/j.1937-5956.2006.tb00243.x |
| [14] | Chen, B., Lee, C.Y.: Logistics scheduling with batching and transportation. Eur. J. Oper. Res. 189(3), 871-876 (2008) · Zbl 1146.90027 · doi:10.1016/j.ejor.2006.11.047 |
| [15] | Li, C.L., Vairaktarakis, G., Lee, C.Y.: Machine scheduling with deliveries to multiple customer locations. Eur. J. Oper. Res. 164(1), 39-51 (2005) · Zbl 1132.90329 · doi:10.1016/j.ejor.2003.11.022 |
| [16] | Chen, Z.L.: Integrated production and outbound distribution scheduling: review and extensions. Oper. Res. 58(1), 130-148 (2010) · Zbl 1233.90151 · doi:10.1287/opre.1080.0688 |
| [17] | Yin, Y.Q., Wang, Y., Cheng, T.C.E., Wang, D.J., Wu, C.C.: Two-agent single-machine scheduling to minimize the batch delivery cost. Comput. Ind. Eng. 92, 16-30 (2016) · doi:10.1016/j.cie.2015.12.003 |
| [18] | Adiri, I., Bruno, J., Frostig, E., Kan, A.H.G.: Rinnooy: single machine flow-time scheduling with a single breakdown. Acta Inform. 26(7), 679-696 (1989) · Zbl 0657.68033 · doi:10.1007/BF00288977 |
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.
