Coordinated scheduling in production, delivery, and storage systems

Abstract

In a typical supply chain, raw materials are transported to factories where items are produced, and finished products are first shipped to warehouses for intermediate storage, and then delivered to retailers or customers. To achieve optimal operational performance in a supply chain, it is critical to schedule the production, delivery and storage operations in a coordinated manner. In this thesis, we present three topics motivated by coordinated scheduling in production, delivery, and storage systems. First, we develop and analyze a single-machine scheduling model that incorporates the scheduling of jobs and the pickup and delivery arrangements of the materials and finished jobs. In this model, there is a capacitated pickup and delivery vehicle that travels between the machine and the storage area, and the objective is to minimize the makespan of the schedule. The problem is strongly NP-hard in general but is solvable in polynomial time when the job processing sequence is predetermined. An efficient heuristic is developed for the general problem. The effectiveness of the heuristic is studied both analytically and computationally. Second, we consider a scheduling model with two machines at different locations. Each job is composed of two tasks where each task must be processed by a specific machine. The finished tasks are shipped to a distribution center in batches before they are bundled together and delivered to customers. The objective is to minimize the sum of the delivery cost and customers' waiting costs. This model attempts to coordinate the production and delivery schedules on the decentralized machines while taking into consideration the shipping cost as well as the waiting time of the customers. We develop polynomial-time heuristic algorithms for this problem and analyze their worst-case performance. Computational experiments are conducted to test the effectiveness of the heuristics and to evaluate the benefits obtained by coordinating the production and delivery of the two decentralized machines. Third, we consider the scheduling of truck arrivals at an air cargo terminal. By coordinating arrivals of cargo delivery trucks with outbound flight departure schedules, some of the shipments can be transferred directly to the departing flights, while others will be stored at the terminal's storage facility and incur extra handling and storage costs. The objective is to obtain a feasible schedule so as to minimize the total cost of operations. We formulate the problem as a time-indexed integer program and show that, with limited number of unloading docks at the terminal, the problem is non-trivial (NP-hard in the strong sense). Our solution methods include an exact solution procedure to determine an optimal unloading sequence for the shipments carried by each truck, together with a Lagrangian relaxation based heuristic for assigning trucks to truck docks and determining truck arrival times. We conducted computational experiments to test the performance of our solution methods. Our simulation results indicate that the proposed scheduling approach has the potential to generate significant cost savings over a first-come, first-served approach currently used at the air cargo terminal that we observed.