Search

We study an integrated charge batching and casting width selection problem arising in the continuous casting operation of the steelmaking process at Shanghai, China based Baosteel. This decision-making problem is not unique to Baosteel; it exists in every large iron and steel company in the world. We collaborated with Baosteel on this problem from 2006 to 2008 by developing and implementing a decision support system (DSS) that replaced their manual planning method. The DSS is still in active use at Baosteel. This paper describes the solution algorithms we developed and imbedded in the DSS. For the general problem that is strongly NP-hard, a column generation-based branch-and-price (B&P) solution approach is developed to obtain optimal solutions. By exploiting the problem structure, efficient dynamic programming algorithms are designed to solve the subproblems involved in the column generation procedure. Branching strategies are designed in a way that ensures that after every stage of branching the structure of the subproblems is preserved such that they can still be solved efficiently. We also consider a frequently occurring case of the problem where each steel grade is incompatible with any other grade. For this special case, a two-level polynomial-time algorithm is developed to obtain optimal solutions. Computational tests on a set of real production data as well as on a more diverse set of randomly generated problem instances show that our algorithms outperform the manual planning method that Baosteel used to use by a significant margin both in terms of tundish utilization for almost every case, and in terms of total cost for most cases. Consequently, by replacing their manual method with our DSS, the estimated benefits to Baosteel include an annual cost saving of about US $1.6 million and an annual revenue increase of about US $3.25 million. [ABSTRACT FROM AUTHOR]

We study conflict and cooperation issues in supply chain manufacturing. Consider an assembly system where suppliers provide parts to a manufacturer. A product cannot be delivered until all its parts have been supplied. The manufacturer performs nonbottleneck operations, for example, outsourced assembly, packaging, and delivery for each product. Two classical scheduling objectives are considered: minimization of the total completion time and of the maximum lateness. We analyze how tar from optimal the best schedule for a suppliers' scheduling problem can be for the corresponding manufacturer's problem, and vice versa. To resolve these conflicts, we consider four alternative scenarios for the relative bargaining power of the suppliers and the manufacturer, and in each case describe a practical mechanism for cooperation between the decision makers. Evaluating the cost of conflict and the benefit of cooperation in these scenarios requires the solution of various scheduling problems by the suppliers, the manufacturer, and the overall system. For all these scheduling problems, we provide either an efficient algorithm or a proof of intractability. Moreover, for two problems that we show are intractable, we describe heuristics and analyze their worst case performance or demonstrate asymptotic optimality of their solutions. We demonstrate computationally that the cost saving realized by cooperation between the decision makers is significant in many cases. Extensions of our models to consider bottleneck operations at the manufacturer and transportation times are also developed. [ABSTRACT FROM AUTHOR]

We consider the supply chain of a manufacturer who produces time-sensitive products that have a large variety, a short life cycle, and are sold in a very short selling season. The supply chain consists of multiple overseas plants and a domestic distribution center (DC). Retail orders are first processed at the plants and then shipped from the plants to the DC for distribution to domestic retailers. Due to variations in productivity and labor costs at different plants, the processing time and cost of an order are dependent on the plant to which it is assigned. We study the following static and deterministic order assignment and scheduling problem faced by the manufacturer before every selling season: Given a set of orders, determine which orders are to be assigned to each plant, find a schedule for processing the assigned orders at each plant, and find a schedule for shipping the completed orders from each plant to the DC, such that a certain performance measure is optimized. We consider four different performance measures, all of which take into account both delivery lead time and the total production and distribution cost. A problem corresponding to each performance measure is studied separately. We analyze the computational complexity of various cases of the problems by either proving that a problem is intractable or providing an efficient exact algorithm for the problem. We propose several fast heuristics for the intractable problems. We analyze the worst-case and asymptotic performance of the heuristics and also computationally evaluate their performance using randomly generated test instances. Our results show that the heuristics are capable of generating near-optimal solutions quickly. [ABSTRACT FROM AUTHOR]

We give a counterexample to show that the optimality proof by Kise et al. (1978) for an algorithm for a scheduling problem is incorrect. [ABSTRACT FROM AUTHOR]