LOGISTICS SCHEDULING: ANALYSIS OF TWO-STAGE PROBLEMS

作     者：Yung-Chia CHANG Chung-Yee LEE 

作者机构：Davicom America Corporation 1135 Kern Avenue Sunnyvale CA 94085 U.S.A.Department of Industrial Engineering and Engineering Management Hong Kong University of Science & Technology Clear Water Bay Kowloon Hong Kong 

出 版 物：《Systems Science and Systems Engineering》 (系统科学与系统工程学报（英文版）)

年 卷 期：2003年第12卷第4期

页      面：385-407页

核心收录：

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Hong Kong RGC Grant HKUST 6010/02E 

主　　题：Logistics scheduling worst case analysis dynamic programming 

摘      要：This paper studies the coordination effects between stages for scheduling problems where decision-making is a two-stage process. Two stages are considered as one system. The system can be a supply chain that links two stages, one stage representing a manufacturer; and the other, a distributor It also can represent a single manufacturer, while each stage represents a different department responsible for a part of operations. A problem that jointly considers both stages in order to achieve ideal overall system performance is defined as a system problem. In practice, at times, it might not be feasible for the two stages to make coordinated decisions due to (i) the lack of channels that allow decision makers at the two stages to cooperate, and/or (ii) the optimal solution to the system problem is too difficult (or costly) to achieve. Two practical approaches are applied to solve a variant of two-stage logistic scheduling problems. The Forward Approach is defined as a solution procedure by which the first stage of the system problem is solved first, followed by the second stage. Similarly, the Backward Approach is defined as a solution procedure by which the second stage of the system problem is solved prior to solving the first stage. In each approach, two stages are solved sequentially and the solution generated is treated as a heuristic solution with respect to the corresponding system problem. When decision makers at two stages make decisions locally without considering consequences to the entire system, ineffectiveness may result - even when each stage optimally solves its own problem. The trade-off between the time complexity and the solution quality is the main concern. This paper provides the worst-case performance analysis for each approach.