Supply chain optimization in the newspaper industry: Integrated production allocation, scheduling and distribution

One of the defining characteristics of the newspaper industry is that the products are virtually worthless at the end of the day; nobody wants to pay for yesterday s news. In addition, strict delivery deadlines and no inventory lead to very short time frames for production and distribution. Consequently production and outbound distribution are intimately linked and should be coordinated in order to achieve the objective of on-time delivery performance at minimum total cost. The increase in online publishing the last decade has led to a general drop in circulation numbers and reduction of advertising revenues. Another consequence of online publishing is that the pressure to include last minute news in the printed editions has been somewhat reduced. There are several unresolved logistical problems in the media industry, for instance the question of where to produce which products in order to optimize the distribution. In Norway it is common for media corporations to collaborate on distribution, but there is little cooperation with respect to where products should be printed.The purpose of this thesis is to develop a model that can be used to identify cost saving potentials in the newspaper industry. We formulate a deterministic cost minimization arc- flow model that integrates facility location, production allocation, production scheduling and vehicle routing for the first echelon of the distribution. The model includes multiple facilities and products, production in time slots, changeover times between production of different products, split deliveries, a heterogeneous vehicle fleet and delivery time windows.The arc-flow model is reformulated to a path-flow formulation using Dantzig-Wolfe decom- position (DWD). Two different decomposition strategies are developed. The first strategy decomposes into two subproblems (D2SP), one for the production and scheduling which is solved for each facility, and one for the vehicle routing which is solved for each vehicle and route. The second decomposition strategy (D1SP) includes the production allocation and scheduling in the master problem while the vehicle routing is in the subproblem.Feasible routes are generated a priori and column generation is used to solve the linear programming (LP) relaxation of the integer programming (IP) problem. Different column generation procedures for the vehicle routing subproblem have been tested for each of the decomposed models. Procedures that add fewer columns per iteration reduce the solution time for the root node by over 50% for both of the decomposed path-flow models. The way in which vehicles and routes are ordered for solving the vehicle routing subproblems also influences the solution time.DWD and general Branch and Bound does not guarantee optimality, or even feasible integer solutions, for IP problems. With the aim of improving the IP solution, two fixing strategies that allow for additional column generation after the root node is solved are implemented in both of the path-flow models. The fixing strategies successively fix vehicles to facilities or routes and re-apply column generation. For D2SP, fixing vehicles to routes improves the communication between the two subproblems which improves the integer solution consider- ably. D1SP performs better than D2SP due to a more integrated formulation and so the fixing strategies do not improve the integer solution found through Branch and Bound. A comparison of the three models reveals that the arc-flow model is better at finding feasible solutions on small instances, while D1SP is the better choice for larger instances. Both of theiidecomposed models provide better LP bounds than the arc-flow model, with D2SP providing by far the best bound.D1SP is able to find good solutions within a reasonable time frame, and is used to conduct an economic analysis on a case from the newspaper industry in South-Eastern Norway. Two of the largest printing facilities in Norway are considered: Amedia s printing facility at Stokke and Schibsted s printing facility in Nydalen, and seven of Amedia and Schibsted s largest newspaper titles. An analysis of the effect of cooperation between Amedia and Schibsted with respect to printing demonstrates that there lies a significant value in cooperating. Full cooperation with traditional offset printing results in a more centralized production and a 9% decrease in distribution costs due to a 24% reduction in the distance driven. The effect of digitalizing the printing process has also been studied. The biggest obstacle for changing to digital printers today is the print rate. However, technology for digital print is improving rapidly and with increased production rates digital print can lead to more efficient routing and considerable reductions in distribution costs. This is due to an increased flexibility in production allocation and scheduling which leads to production closer to customers. Mov- ing the newsroom deadline forward amplifies the effects of cooperation and digitalization, decreasing the distribution costs further.The numeric findings are case-specific and our model only considers costs, excluding other factors that are important in decision making, such as e.g. the media corporations marketing strategies, environmental and social aspects.It is worth mentioning that our model is not only applicable for the newspaper industry but can with certain modifications be used for problems in other industries with time-sensitive products. The model is especially useful if integration of production allocation, scheduling and distribution is important in order to minimize facility or production costs and optimize distribution