Coordinating Order Acceptance and Batch Delivery for an Integrated Supply Chain Scheduling


1 Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

2 Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran


This paper develops Order Acceptance for an Integrated Production-Distribution Problem in which Batch Delivery is implemented. The aim of this problem is to coordinate: (1) rejecting some of the orders (2) production scheduling of the accepted orders and (3) batch delivery to maximize Total Net Profit. A Mixed Integer Programming is proposed for the problem. In addition, a hybrid meta-heuristic algorithm is developed. For a quick exploration around a solution, a Local search is proposed. Two simple heuristics for initial population and a heuristic for batching are proposed. Besides, data is generated to evaluate the performance of algorithms and compare with each other based on comprehensive experiments.


1.     Nahavandi, N., Zegordi, S. and Abbasian, M., "Solving the dynamic job shop scheduling problem using bottleneck and intelligent agents based on genetic algorithm", International Journal of Engineering-Transactions C: Aspects,  Vol. 29, No. 3, (2016), 347-352.
2.     Hamta, N., Ghomi, S.F., Bahalke, U. and Golpaigani, H., "Single machine scheduling problem with precedence constraints and deteriorating jobs", International Journal of Engineering-Transactions A: Basics,  Vol. 24, No. 2, (2011), 115-122.
3.     Chen, Z.-L., "Integrated production and outbound distribution scheduling: Review and extensions", Operations Research,  Vol. 58, No. 1, (2010), 130-148.
4.     Vroblefski, M., Ramesh, R. and Zionts, S., "Efficient lot-sizing under a differential transportation cost structure for serially distributed warehouses", European Journal of Operational Research,  Vol. 127, No. 3, (2000), 574-593.
5.     Gao, S., Qi, L. and Lei, L., "Integrated batch production and distribution scheduling with limited vehicle capacity", International Journal of Production Economics,  Vol. 160, No., (2015), 13-25.
6.     Yin, Y., Cheng, T., Hsu, C.-J. and Wu, C.-C., "Single-machine batch delivery scheduling with an assignable common due window", Omega,  Vol. 41, No. 2, (2013), 216-225.
7.     Rasti-Barzoki, M. and Hejazi, S.R., "Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries for multiple customers in supply chains", European Journal of Operational Research,  Vol. 228, No. 2, (2013), 345-357.
8.     Rasti-Barzoki, M. and Hejazi, S.R., "Pseudo-polynomial dynamic programming for an integrated due date assignment, resource allocation, production, and distribution scheduling model in supply chain scheduling", Applied Mathematical Modelling,  Vol. 39, No. 12, (2015), 3280-3289.
9.     Mazdeh, M.M., Shashaani, S., Ashouri, A. and Hindi, K.S., "Single-machine batch scheduling minimizing weighted flow times and delivery costs", Applied Mathematical Modelling,  Vol. 35, No. 1, (2011), 563-570.
10.   Zhong, X. and Jiang, D., "Integrated scheduling of production and distribution with release dates and capacitated deliveries", Mathematical Problems in Engineering,  Vol. 2016, (2016).
11.   Sanei, M., Mahmoodirad, A., Niroomand, S., Jamalian, A. and Gelareh, S., "Step fixed-charge solid transportation problem: A lagrangian relaxation heuristic approach", Computational and Applied Mathematics,  (2015), 1-21.
12.   Sahraeian, R. and Zabihi, F., "Trucks scheduling in a multi-product cross docking system with multiple temporary storages and multiple dock doors", International Journal of Engineering-Transactions B: Applications,  Vol. 29, No. 11, (2016), 1595-1562.
13.   Guerrero, H.H. and Kern, G.M., "How to more effectively accept and refuse orders", Production and Inventory Management,  Vol. 29, No. 4, (1988), 59-63.
14.   Slotnick, S.A., "Order acceptance and scheduling: A taxonomy and review", European Journal of Operational Research,  Vol. 212, No. 1, (2011), 1-11.
15.   Nobibon, F.T. and Leus, R., "Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment", Computers & Operations Research,  Vol. 38, No. 1, (2011), 367-378.
16.   Og, C., Salman, F.S. and Yalçın, Z.B., "Order acceptance and scheduling decisions in make-to-order systems", International Journal of Production Economics,  Vol. 125, No. 1, (2010), 200-211.
17.   Cesaret, B., Oğuz, C. and Salman, F.S., "A tabu search algorithm for order acceptance and scheduling", Computers & Operations Research,  Vol. 39, No. 6, (2012), 1197-1205.
18.   Wang, X., Xie, X. and Cheng, T., "Order acceptance and scheduling in a two-machine flowshop", International Journal of Production Economics,  Vol. 141, No. 1, (2013), 366-376.
19.   Esmaeilbeigi, R., Charkhgard, P. and Charkhgard, H., "Order acceptance and scheduling problems in two-machine flow shops: New mixed integer programming formulations", European Journal of Operational Research,  (2015).
20.   Lin, S.-W. and Ying, K.-C., "Order acceptance and scheduling to maximize total net revenue in permutation flowshops with weighted tardiness", Applied Soft Computing,  Vol. 30, (2015), 462-474.
21.   Rahman, H.F., Sarker, R. and Essam, D., "A real-time order acceptance and scheduling approach for permutation flow shop problems", European Journal of Operational Research,  Vol. 247, No. 2, (2015), 488-503.
22.   Lei, D. and Guo, X., "A parallel neighborhood search for order acceptance and scheduling in flow shop environment", International Journal of Production Economics,  Vol. 165, (2015), 12-18.
23.   Emami, S., Moslehi, G. and Sabbagh, M., "A benders decomposition approach for order acceptance and scheduling problem: A robust optimization approach", Computational and Applied Mathematics,  (2016), 1-45.
24.   Wang, X., Huang, G., Hu, X. and Cheng, T.E., "Order acceptance and scheduling on two identical parallel machines", Journal of the Operational Research Society,  Vol. 66, No. 10, (2015), 1755-1767.
25.   Thevenin, S., Zufferey, N. and Potvin, J.-Y., A multi-coloring approach for an order acceptance and scheduling problem with preemption and job incompatibilities. (2013), Technical report, CIRRELT--45.
26.   Noroozi, A., Mokhtari, H. and Abadi, I.N.K., "Research on computational intelligence algorithms with adaptive learning approach for scheduling problems with batch processing machines", Neurocomputing,  Vol. 101, (2013), 190-203.
27.   Ghosh, J.B., "Job selection in a heavily loaded shop", Computers & Operations Research,  Vol. 24, No. 2, (1997), 141-145.
28.   Herbots, J., Herroelen, W. and Leus, R., "Dynamic order acceptance and capacity planning on a single bottleneck resource", Naval Research Logistics (NRL),  Vol. 54, No. 8, (2007), 874-889.
29.   Park, J., Nguyen, S., Zhang, M. and Johnston, M., "Genetic programming for order acceptance and scheduling", in Evolutionary Computation (CEC), IEEE Congress, (2013), 1005-1012.
30.   Xiao, Y.-Y., Zhang, R.-Q., Zhao, Q.-H. and Kaku, I., "Permutation flow shop scheduling with order acceptance and weighted tardiness", Applied Mathematics and Computation,  Vol. 218, No. 15, (2012), 7911-7926.
31.   Qi, L., Jiang, D. and Wang, Z., "A modified discreet particle swarm optimization for a multi-level emergency supplies distribution network",  (2016).
32.   A. Shahbahrami, S.J.a.S.H.S.Z., " Parallel implementation of particle swarm optimization variants using graphics processing unit platform", International Journal of Engineering,  Vol. 30, No. 1, (2017), 48-56.
33.   Mehta, S.V. and Uzsoy, R., "Minimizing total tardiness on a batch processing machine with incompatible job families", IIE Transactions,  Vol. 30, No. 2, (1998), 165-178.
34.   Morton, T. and Vepsalainen, A., "Priority rules and leadtime estimation for job shop scheduling with weighted tardiness costs", Management Science,  Vol. 33, (1987), 1036-1047.
35.   M’Hallah, R., "Minimizing total earliness and tardiness on a single machine using a hybrid heuristic", Computers & Operations Research,  Vol. 34, No. 10, (2007), 3126-3142.
36.   Pindeo, M., "Scheduling: Theory, algorithms, and systems", Prentice Hall, USA,  (2002).
37.   Gordon, V., Proth, J.-M. and Chu, C., "A survey of the state-of-the-art of common due date assignment and scheduling research", European Journal of Operational Research,  Vol. 139, No. 1, (2002), 1-25.