As a growing number of manufacturers adopt the make-to-order business mode and a growing number of retailers sell online, we are seeing numerous decision problems that can be modeled as what are known in the literature as integrated production and distribution scheduling (IPDS) problems. In such problems, order processing and delivery must be scheduled jointly in order to achieve an optimal balance between total operational costs and overall customer service. Offline IPDS problems, in which the information about every order is known in advance with certainty, are extensively studied. However, research on online IPDS problems, in which orders arrive randomly with their information unknown until they arrive, is relatively recent but is growing rapidly. In this paper, we first describe several real-world applications to illustrate the importance of studying online IPDS problems from a practical point of view. We then review the existing literature on online IPDS problems with a focus on existing online algorithms for these problems and their theoretical performance. We also derive some new results to fill several gaps left in the literature and discuss possible topics for future research. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0305 .

We study integrated production- and delivery-scheduling problems that arise in practical make-to-order settings in several industries. In these problems, make-to-order products are first processed in a plant and then delivered to customer sites through two stages of shipping: first, from the plant to a pool point (e.g., a port, a distribution, or a consolidation center) and, second, from the pool point to customer sites. The objective is to obtain a joint schedule of job processing at the plant and two-stage shipping of completed jobs to customer sites to optimize a performance measure that takes into account both delivery timeliness and total transportation costs. We consider two problems in which delivery timeliness is measured by total or maximum lead time of the jobs and study both offline and online versions of these problems. For the offline problems involving a single production line at the plant, we provide optimal dynamic programming algorithms. For the more general offline problems involving multiple production lines at the plant, we propose fast heuristics and analyze their worst-case and asymptotic performances. For the online problems, we propose online algorithms and analyze their competitive ratios. By comparing our offline heuristics with lower bounds using randomly generated test instances, it is shown that these heuristics are capable of generating near-optimal solutions quickly. Using real data from Baosteel’s Meishan plant, we also show that our corresponding offline heuristic generates significantly better solutions than Baosteel’s rule-based approach. In addition, our computational results on the performance of the online algorithms relative to the offline heuristics generate important methodological insights that can be used by practitioners in choosing a specific solution approach.

We consider several integrated production, inventory, and delivery problems that arise in a number of practical settings where customer orders have pre-specified delivery time windows. These orders are first processed in a plant and then delivered to the customers by transporters (such as trains and air flights) which have fixed delivery departure times. If an order is completed but not immediately delivered by a transporter, the order is kept temporarily in inventory, which incurs an inventory cost. There is a delivery cost for delivering an order, which varies with the departure time. Given a set of orders, the objective is to find an integrated schedule for processing the orders, keeping finished orders in inventory if necessary, and delivering them to the customers such that the total inventory and delivery cost is minimum. We consider two classes of problems: where order delivery is splittable and where order delivery is nonsplittable. For each of the problems considered, we study its computational complexity by either showing that the problem is NP-hard or proposing an algorithm that can find an optimal solution. For the two most general problems, we show that any polynomial time algorithm has an arbitrarily bad worst-case performance bound, and propose combined column generation and tabu search heuristic algorithms that can find near optimal solutions for them in a reasonable computational time. The online appendix is available at https://doi.org/10.1287/ijoc.2016.0726 .

We consider a class of problems of scheduling n jobs on m identical, uniform, or unrelated parallel machines with an objective of minimizing an additive criterion. We propose a decomposition approach for solving these problems exactly. The decomposition approach first formulates these problems as an integer program, and then reformulates the integer program, using Dantzig-Wolfe decomposition, as a set partitioning problem. Based on this set partitioning formulation, branch-and-bound exact solution algorithms can be designed for these problems. In such a branch-and-bound tree, each node is the linear relaxation problem of a set partitioning problem. This linear relaxation problem is solved by a column generation approach where each column represents a schedule on one machine and is generated by solving a single machine subproblem. Branching is conducted on variables in the original integer programming formulation instead of variables in the set partitioning formulation such that single machine subproblems are more tractable. We apply this decomposition approach to two particular problems: the total weighted completion time problem and the weighted number of tardy jobs problem. The computational results indicate that the decomposition approach is promising and capable of solving large problems.

An example is presented to show that the worst-case complexity of Bertsekas' small-label-first strategy for the shortest path problem is exponential. It becomes polynomial if, when scanning a node i, its successors j ϵ Γ(i) are examined in the nondecreasing order of dij, the distance between i and j. © 1997 John Wiley & Sons, Inc. Networks, 29: 111–116, 1997