A memetic algorithm for joint production and distribution scheduling with due dates

Abstract

Integration between production and distribution phases in supply chain has attracted close attention of many researchers over the last decade as companies have to juggle these activities for survival in increasingly competitive market conditions. In this paper, we study a joint production and distribution problem where a single manufacturer has committed to processing jobs (i.e., customer orders) on permutation flow-shop environment and subsequently distributing them by a single capacitated vehicle. Customers locate geographically-dispersed points and place their orders with pre-determined due dates. Since a single vehicle is available, customer orders should be consolidated in order to reduce the total trip time spent by the vehicle but this may result in failing to meet some of customer orders before their due dates. The objective is therefore minimizing the total travelling time plus total tardiness. We first develop a mixed integer linear programming to formulate the problem. Due to intractability matters, mathematical formulation suffers to find optimal solutions even in moderate number of customers. Thus, we present a memetic algorithm (MA) to find good or near-optimal solutions in an acceptable amount of time. In order to evaluate the effectiveness of the algorithm, we compare CPLEX results with that of the MA on a wide range of randomly generated test instances. Results indicate that MA is capable of finding solutions to optimality in a quite short time for most of the small-sized instances. For medium and large-sized instances, MA is still well-performing and yields better solutions as compared to CPLEX solutions found 3 h time limit.