Integrated hybrid flow shop scheduling and vehicle routing problem

Document Type : Research Paper


Industrial engineering department, Faculty of engineering, University of Kurdistan, Sanandaj, Iran


In this paper, a new integrated mathematical model for production and distribution planning is presented to minimize tardiness and transportation costs. A mixed-integer linear programming (MILP) formulation is developed for the problem which consists of two parts. First, the production scheduling in a hybrid flow shop (HFS) environment with identical machines in each stage, and then, the delivery of completed jobs with a fleet of vehicles that have the same capacity. Due to the NP-hard nature of the problem, a new metaheuristic approach based on Particle Swarm Optimization Algorithm (PSO) and Genetic Algorithm (GA) is presented to solve the integrated problem. GA’s operators are used to update the particle position of the PSO algorithm. The algorithm uses dispatching rules to represent the initial solution and searches in the solution space including active schedules. To investigate the efficiency and effectiveness of the proposed method, numerical studies are carried out with random problems. The computational results show that the proposed solution approach yields fairly good results in comparison with the PSO versions in the subject literature. The algorithm is capable of generating relatively good solutions for sample cases.


Main Subjects

Ahmadi Zar F., Hosseinabadi Farahani M., (2012), A novel hybrid genetic algorithm for the open shop scheduling problem, International Journal of Advanced Manufacturing Technology, 62, 775-787.
Ahmadizar F., Farhadi S., (2015). Single-machine batch delivery scheduling with job release dates, due windows and earliness, tardiness, holding and delivery costs, Computers & Operations Research, 53, 194-205.
Alba E., Dorronsoro B. (2004). Solving the Vehicle Routing Problem by Using Cellular Genetic Algorithms, Lecture Notes in Computer Science, (vol 3004). Springer, Berlin, Heidelberg.
Alvarez E., Díaz F., Osaba E., (2015), A multi-agent approach for dynamic production and distribution scheduling. Int. J. Engineering Management and Economics, 1, 1-20.
Amorim p., Belo-Filho M.A.F, Toledo F.M.B., Almeder C., Almada-Lobo B., (2013), Lot sizing versus batching in the production and distribution planning of perishable goods. Int. J. Production Economics, 146, 208–218.
Chen H.K., Hsueh C.F., Chang M.S., (2009), Production scheduling and vehicle routing with time windows for perishable food products, Computers & Operations Research. 36, 2009, 2311–2319.
Chen Z-L., (2010), Integrated Production and Outbound Distribution Scheduling. Review and Extensions Operations Research, 58(1), 130-148.
Chieu Ta Q., Billaut J.Ch., Bouquard J.L., (2015), Heuristic algorithms to minimize the total tardiness in a flow shop production and outbound distribution scheduling problem. Presented at the 6th IESM Conference, October 2015, Seville, Spain.
Choudhary K., Gautam G., Bharti N., Rathore V.S., (2019), Particle Swarm Optimization for Flexible Job Scheduling Problem with Mutation Strategy, Computing and Network Sustainability, 75,  pp 497-503.
Diveev, A.I., Bobr O.V., (2017), Variational Genetic Algorithm for NP-hard Scheduling Problem Solution, Procedia Computer Science, 103, 52–58.
Eberhart R.C., Shi Y., (2000), Comparing inertia weights and constriction factors in particle swarm optimization, In Proceedings of Congress on Evolutionary Computing, 84–88.
Gen M., Cheng R., Genetic Algorithms and Engineering Design, Wiley, New York.
He S., Wu Q.H., Wen J.Y., Saunders J.R., Paton R.C., (2004), A particle swarm optimizer with passive congregation. BioSystems, 78, 135–147.
Ho W., Ho G.T.S., Ji P., Lau H.C.W., (2008), A hybrid genetic algorithm for the multi-depot vehicle routing problem, Engineering Applications of Artificial Intelligence, 21, 548–557.
Jamrus T., Chien Ch., (2018), Hybrid Particle Swarm Optimization Combined With Genetic Operators for Flexible Job-Shop Scheduling Under Uncertain Processing Time for Semiconductor Manufacturing, IEEE Transactions on semiconductor manufacturing, 31(1).
Johar F., Nordin S. Z., Potts C.N., (2016), Coordination of Production Scheduling and Vehicle Routing Problem with Due Dates. American Institute of Physics Conference Proceedings, 1750(1), 1–9.
Karimi N., Davoudpour H., (2015), A branch and bound method for solving multi-factory supply chain scheduling with batch delivery. Expert Systems with Applications, 42, 238–245.
Kaweegitbundit P., (2012), Evaluation Dispatching Rules for Two-Stage Hybrid Flow Shop Scheduling with Parallel Machines, Applied Mechanics and Materials, 152, 1487-1491.
Kennedy J., Eberhart R., (1997), A discrete binary version of the particle swarm algorithm, In Proceedings of the 1997 IEEE international conference on systems, 5, 4104– 4108.
Kennedy J., Eberhart R., (1995), Particle swarm optimization, In Proceedings of the 1995 IEEE international conference on neural network, 4)4(, 1942– 1948.
Kennedy J., Eberhart R.C., Shi Y., (2001), Swarm Intelligence, (Morgan Kaufmann: CA).
Kim Y.D., (1993), A new branch and bound algorithm for minimizing mean tardiness in 2-machine flow shops. Computers and Operations Research, 20, 391– 401.
Kumar R.S., Kondapaneni K., Dixit V., Goswami A., Thakur L.S., Tiwari M.K., (2015), Multi-objective modeling of production and pollution routing problem with time window: A self-learning particle swarm optimization approach. Computers & Industrial Engineering, 1-38.
Lacomme Ph., Moukrim A., Quilliot A., Vinot M., (2016), The Integrated Production and Transportation Scheduling Problem based on a GRASP×ELS resolution scheme. International Federation of Automatic Control, 49(12), 1466-1471.
Liao C.J., Tseng C.T., Luarn P., (2007), A discrete version of particle swarm optimization for flow shop scheduling problems, Comput Oper Res, 34, 3099–3111.
Low C., Chang C.M., Li R.K., and Huang C.L., (2014), Coordination of production scheduling and delivery problems with heterogeneous fleet. International Journal of Production Economics. 153(0), 139 -148.
Mirabi M., (2014), A novel hybrid genetic algorithm to solve the sequence-dependent permutation flow-shop scheduling problem, International Journal of Advanced Manufacturing Technology, 71, 429–437.
Moons, S., Ramaekers, K., Caris, A., Arda, Y., (2017), Integrating production scheduling and vehicle routing decisions at the operational decision level: a review and discussion, Computers & Industrial Engineering, 104, 224-245.
Niu Q., Zhou F., Zhou T., (2010), Quantum Genetic Algorithm for Hybrid Flow Shop Scheduling Problems to Minimize Total Completion Time., International Conference on Intelligent Computing for Sustainable Energy and Environment, 21-29.
Oguz C., Ercan M., (2005), A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks, J.Scheduling, 8(4), 323-351.
Oguz C., Zinder Y., Do V.H., Janiak A., Lichtenstein M., (2004), Hybrid flow-shop scheduling problems with multiprocessor task systems, European Journal of Operational Research, 152(1), 115-131.
Pan Q.K., Tasgetiren M.F., Liang Y.CH., (2008), A discrete particle swarm optimization algorithm for the no-wait flow shop scheduling problem, Computers & Operations Research, 35, 2807 – 2839.
Ramezanian R., Mohammadi Sh., Cheraghalikhani A., (2017), Toward an integrated modeling approach for production and delivery operations in flow shop system: Trade-off between direct and routing delivery methods, Journal of Manufacturing Systems, 44, 79–92.
Rohmer S., Billaut J.CH., (2015), Production and outbound distribution scheduling: a two-agent approach. Presented at the 6th IESM Conference, Seville, Spain.
Serifoglu F.S., Ulusoy G., (2004), Multiprocessor task scheduling in multistage hybrid flow shops: a genetic algorithm approach, J. Oper. Res. Soc, 55, 504–512.
Shi Y., Eberhart R.C., (1998), A modified particle swarm optimizer, in Proceedings of the IEEE Congress on Evolutionary Computation, 1998, 69–73.
Tasgetiren M.F., Sevkli M., Liang Y.C., Gencyilmaz G., (2004), Particle swarm optimization algorithm for single machine total weighted tardiness problem, in Proceeding of the IEEE Congress on Evolutionary Computation, 1412–1419.