Solution approaches for integrated production and distribution scheduling problems

Considering that competition takes place between the supply chains of businesses rather than businesses today, effective management of functions in the supply chain is highly important for businesses. Production and distribution are two main functions in the supply chain. In the traditional approach, these functions are evaluated individually and considered hierarchically. These hierarchically made decisions cannot guarantee optimal in terms of the system. For this reason, production and distribution operations should be handled in an integrated manner to achieve the global optimal in terms of the supply chain. In addition to its economic advantages, it has been inevitable for some cases to consider production and distribution operations in an integrated manner in the supply chain. There are many application areas where production and distribution operations are handled in an integrated manner in real life. Production and distribution of perishable and time-sensitive products is one of these application areas. In the thesis, the integration of production and distribution operations at the operational level has been examined. This problem, which includes the production scheduling problem in the production phase, and the vehicle routing problem in the distribution phase, is called as "Integrated Production and Distribution Scheduling (IPDS) Problem" in the literature. In the thesis study, three different problems have been addressed within the scope of IPDS. In the problem expressed as the Permutation Flow Shop Production Environment and the Single Vehicle Distribution Environment (PFS-SV) IPDS Problem, a permutation flow shop production environment where orders visit all machines placed in series in the same order and a distribution environment where orders are delivered with a single vehicle with limited capacity are analyzed. In the second problem expressed as the Permutation Flow Shop Production Environment and the Multi Vehicle Distribution Environment (PFS-MV) IPDS Problem, the same production environment and the distribution environment with more than one vehicle with heterogeneous capacity are examined by taking into account the more general form of the first problem. Finally, in the last problem expressed as the Job Shop Production Environment and the Multi Vehicle Distribution Environment (JS-MV) IPDS Problem, the job shop production environment where the operation sequences of the orders are different from each other and the distribution environment with multi vehicles with heterogeneous capacity are examined. Due to the limited number of vehicles in all three types of problems, some customer orders may be delivered after the predefined due date, thus there is tardiness for these orders. In PFS-SV and PFS-MV Problems, when the due dates of the customers are large enough, the distribution process is requested to be completed as soon as possible. Therefore, the objective for PFS-SV and PFS-MV Problems are considered minimizing the sum of total tour time and total tardiness. JS-MV Problem, on the other hand, has been investigated in a multi-objective structure by including environmental factors into the problem, as minimizing the total CO2 emission released into the air by vehicles and minimizing the maximum tardiness. In all three problems, the vehicles in the system can be used more than once during the planning period. All three problems addressed within the scope of the thesis have not been encountered before in the literature and have been examined for the first time in this thesis study. For PFS-SV Problem, a Mixed Integer Linear Programming (MILP) model has been developed by defining the assumptions and constraints of the problem. Due to the NP-hard structure of the problem, the Memetic Algorithm (MA) approach has been proposed to obtain optimal or near-optimal solutions in a reasonable time for big-sized problems. 1080 test instances have been created in small, medium, and big-sized according to the number of customers to evaluate the performance of the solution methods proposed for PFS-SV Problem. In only 256 of the 1080 instances examined, the optimal solution can be obtained with CPLEX within three hours. 243 of these 256 instances, optimal solutions are reached by MA in a very short time expressed in seconds. While relative performances of CPLEX and MA are very close to each other in medium-sized problems, when the solution times are evaluated, it has been seen that MA is very effective in terms of solution time. However, in big-sized problems, CPLEX cannot obtain an optimal solution in any instance and the relative performance of CPLEX within the three-hour time limit is found to be significantly lower than MA. Since the Mixed Integer Programming (MIP) model developed for PFS-MV Problem is not linear, the model is first linearized with linearization constraints, then the MA approach developed for PFS-SV Problem is adapted according to PFS-MV Problem because there are multi vehicles in the system. The performance of CPLEX and MA are evaluated on the 1980 test instances developed for PFS-MV Problem. While CPLEX can obtain an upper limit in all instances for PFS-SV Problem, for PFS-MV Problem it can obtain an upper limit for only 388 of 720 big-sized instances within the given time limits. Besides, for PFS-SV Problem, CPLEX was able to obtain the optimal solution for all examples, while for PFS-MV Problem it can obtain the optimal solution for 145 of 180 small-sized problems. As a result, it has been observed that the number of vehicles in the system is more than one increases the complexity of the problem. With the proposed MA for PFS-MV Problem, the optimal values in all 145 instances who's optimal are known were found in a very short time, expressed in seconds. When the relative performances of MA and CPLEX are evaluated, close results have been obtained for PFS-SV in medium-sized problems, while the proposed MA for PFS-MV Problem is found to be more successful in terms of relative performance compared to CPLEX even in the case of 10 customers, and with the increase in the number of customers, MA's relative performance to CPLEX has increased substantially. The developed MA outperformed CPLEX even in the biggest problems in less than a minute. JS-MV Problem has been formulated with a Multi-Objective Mixed Integer Programming model and the Augmented Epsilon Constraint Method (AUGMECON) is applied as the exact method to solve the problem. As the AUGMECON method has become insufficient as the problem size increased, two different heuristic methods, Non-Dominated Sorting Genetic Algorithm-II (NSGA-II) and Pareto Local Search (PLS) have developed for multi-objective optimization problems are applied to JS-MV Problem. In the PLS algorithm, while the variable neighbor search algorithm is applied in the production phase of the problem, the local search approach is used in the distribution phase. The algorithms proposed for JS-MV Problem are compared on 624 randomly generated test instances both with the exact method and with each other. The number of pareto solutions, hypervolume values, and solution times are used as the multi-objective optimization performance criteria. When the results are evaluated, the Pareto fronts obtained with both NSGA-II and PLS approach in small-sized instances are found to be very close to the real Pareto front obtained by AUGMECON. In medium and big-sized problems, since the trade-off matrix cannot be created within the time limit given by AUGMECON, only the relative performance of NSGA-II and PLS to each other has been evaluated. According to the results, NSGA-II is found to be more successful than the PLS compared to the Pareto solutions obtained within the ten-minute time limit in terms of all three-performance criteria. It has been observed that the PLS is very sensitive to the increase in the number of customers, so the PLS is also run for one hour. When the results obtained are examined, it is seen that increasing the solution time significantly increased the performance of the PLS, even in some cases, the PLS has outperformed NSGA-II.