Integrated Scheduling of Production and Two-Stage Delivery of Make-to-Order Products: Offline and Online Algorithms

Lixin Tang (), Feng Li () and Zhi-Long Chen ()
Additional contact information
Lixin Tang: Liaoning Engineering Laboratory of Operations Analytics and Optimization for Smart Industry, Institute of Industrial and Systems Engineering, Northeastern University, Shenyang 110819, China;
Feng Li: School of Management, Huazhong University of Science & Technology, Wuhan 430074, China;
Zhi-Long Chen: Robert H. Smith School of Business, University of Maryland, College Park, Maryland 20742

INFORMS Journal on Computing, 2019, vol. 31, issue 3, 493–514

Abstract: 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.

Keywords: make-to-order; scheduling; delivery; dynamic programming; heuristic; online algorithm; worst-case analysis; asymptotic analysis; competitive ratio analysis (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0842 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:3:p:493-514

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().