A Combinatorial Benders Cut for the Integrated Production Scheduling and Distribution Problem

Document Type : Research Paper


1 college of Engineering, Alborz campus, University of Tehran, Tehran, Iran

2 School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran



One of the most attractive topics for industry and researchers in industrial engineering is the integration of decisions in the supply chain. There are some advantages in the integrated decisions compared to different decisions, such as decreasing the cost of distribution and On-Time delivery. An integrated production scheduling and distribution problem is discussed in this study. The main contribution of this paper is to study this problem from a multi-agent viewpoint. In this case, each agent has a set of customers with their jobs, and each agent has a specific objective. Here, a two-agent problem is discussed in which the first agent objective is the minimization of the total tardiness for jobs of the first agent and the second agent objective is to minimize the total cost of the distribution. For this problem, a mixed-integer linear programming formulation is developed. Due to the complexity of the original problem and its specific structure, a combinatorial Benders decomposition approach decomposes it to the master problem and sub-problem. It means some modifications have been applied to the classic version of Benders method. The results show the excellent performance of the algorithm in comparison with another exact method .


Agnetis, A., Aloulou, M., & Fu, L.L. (2014). Coordination of production and interstage batch delivery with outsourced distributionEuropean Journal of Operational Research, 238(1), 130–142.
Agnetis, A., Pascale, G., & Pacciarelli, D. (2009). A Lagrangian approach to single-machine scheduling problems with two competing agentsJournal of Scheduling, 12(4), 401–415.
Agnetis, A., Mirchandani, P., Pacciarelli, D., & Pacifici, A. (2004). Scheduling problems with two competing agentsOperations research, 52(2), 229–242.
Armstrong, R., Gao, S., & Lei, L. (2008). A zero-inventory production and distribution problem with a fixed customer sequenceAnnals of Operations Research, 159(1), 395–414.
Baker, K., & Smith, J. (2003). A multiple-criterion model for machine schedulingJournal of scheduling, 6(1), 7–16.
Bard, J., & Nananukul, N. (2009). The integrated production–inventory–distribution–routing problemJournal of Scheduling, 12(3), 257.
BnnoBRs, J. (1962). Partitioning procedures for solving mixed-variables programming problems ‘Numerische mathematik, 4(1), 238–252.
Chandra, P., Fisher, M., & others (1994). Coordination of production and distribution planningEuropean journal of operational research, 72(3), 503–517.
Chen, Z.L., & Vairaktarakis, G. (2005). Integrated scheduling of production and distribution operationsManagement Science, 51(4), 614–628.
Cheng, T., Gordon, V., & Kovalyov, M. (1996). Single machine scheduling with batch deliveriesEuropean Journal of Operational Research, 94(2), 277–283.
Cheng, T., & Kahlbacher, H. (1993). Scheduling with delivery and earliness penaltiesAsia-Pacific Journal of Operational Research, 10(2), 145–152.
Codato, G., & Fischetti, M. (2006). Combinatorial Benders' cuts for mixed-integer linear programmingOperations Research, 54(4), 756–766.
Garcia, J., & Lozano, S. (2004). Production and vehicle scheduling for ready-mix operationsComputers & Industrial Engineering, 46(4), 803–816.
Garcia, J., & Lozano, S. (2005). Production and delivery scheduling problem with time windowsComputers & Industrial Engineering, 48(4), 733–742.
Geismar, H., Laporte, G., Lei, L., & Sriskandarajah, C. (2008). The integrated production and transportation scheduling problem for a product with a short lifespanINFORMS Journal on Computing, 20(1), 21–33.
Hall, N., & Potts, C. (2003). Supply chain scheduling: Batching and deliveryOperations Research, 51(4), 566–584.
Hall, N., & Potts, C. (2005). The coordination of scheduling and batch deliveriesAnnals of operations research, 135(1), 41–64.
He, Z., Guo, Z., & Wang, J. (2019). Integrated scheduling of production and distribution operations in a global MTO supply chainEnterprise Information Systems, 13(4), 490–514.
Herrmann, J., & Lee, C.Y. (1993). On scheduling to minimize earliness-tardiness and batch delivery costs with a common due dateEuropean Journal of Operational Research, 70(3), 272–288.
Ji, S.f., Peng, X.s., & Luo, R.j. (2019). An integrated model for the production-inventory-distribution problem in the Physical InternetInternational Journal of Production Research, 57(4), 1000–1017.
Joo, C., & Kim, B. (2017). Rule-based meta-heuristics for integrated scheduling of unrelated parallel machines, batches, and heterogeneous delivery trucksApplied Soft Computing, 53, 457–476.
Lee, C.Y., & Chen, Z.L. (2001). Machine scheduling with transportation considerationsJournal of scheduling, 4(1), 3–24.
Lei, L., Liu, S., Ruszczynski, A., & Park, S. (2006). On the integrated production, inventory, and distribution routing problemIIE Transactions, 38(11), 955–970.
Li, C.L., & Vairaktarakis, G. (2007). Coordinating production and distribution of jobs with bundling operationsIIE transactions, 39(2), 203–215.
Li, C.L., Vairaktarakis, G., & Lee, C.Y. (2005). Machine scheduling with deliveries to multiple customer locationsEuropean Journal of Operational Research, 164(1), 39–51.
Li, K., Zhou, C., Leung, J., & Ma, Y. (2016). Integrated production and delivery with single machine and multiple vehiclesExpert Systems with Applications, 57, 12–20.
Lin, W.C., Yin, Y., Cheng, S.R., Cheng, T., Wu, C.H., & Wu, C.C. (2017). Particle swarm optimization and opposite-based particle swarm optimization for two-agent multi-facility customer order scheduling with ready timesApplied Soft Computing, 52, 877–884.
Marandi, F., & Fatemi Ghomi, S. (2019). Integrated multi-factory production and distribution scheduling applying vehicle routing approachInternational Journal of Production Research, 57(3), 722–748.
Mula, J., Peidro, D., Diaz-Madronero, M., & Vicens, E. (2010). Mathematical programming models for supply chain production and transport planningEuropean Journal of Operational Research, 204(3), 377–390.
Perez-Gonzalez, P., & Framinan, J. (2014). A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problemsEuropean Journal of Operational Research, 235(1), 1–16.
Pundoor, G., & Chen, Z.L. (2005). Scheduling a production–distribution system to optimize the tradeoff between delivery tardiness and distribution costNaval Research Logistics (NRL), 52(6), 571–589.
Pundoor, G., & Chen, Z.L. (2009). Joint cyclic production and delivery scheduling in a two-stage supply chainInternational Journal of Production Economics, 119(1), 55–74.
Tan, Q., Chen, H.P., Du, B., & Li, X.l. (2011). Two-agent scheduling on a single batch processing machine with non-identical job sizes. In 2011 2nd International Conference on Artificial Intelligence, Management Science and Electronic Commerce (AIMSEC) (pp. 7431–7435).
Rohmer, S., & Billaut, J.C. (2015). Production and outbound distribution scheduling: a two-agent approach. In 2015 International Conference on Industrial Engineering and Systems Management (IESM) (pp. 135–144).
Selvarajah, E., Steiner, G., & Zhang, R. (2013). Single machine batch scheduling with release times and delivery costsJournal of Scheduling, 16(1), 69–79.
Stecke, K., & Zhao, X. (2007). Production and transportation integration for a make-to-order manufacturing company with a commit-to-delivery business modeManufacturing & Service Operations Management, 9(2), 206–224.