Single-item production–delivery scheduling problem with stage-dependent inventory costs and due-date considerations

Abstract

This paper studies an integrated scheduling problem for a single-item, make-to-order supply chain system consisting of one supplier, one capacitated transporter and one customer. Specifically, we assume the existence in the production stage of an intermediate inventory that works as a buffer to balance the production rate and the transportation speed. Jobs are first processed on a single machine in the production stage, and then delivered to the pre-specified customer by a capacitated vehicle in the delivery stage. Each job has a due date specified by the customer, and must be delivered to the customer before its due date. Moreover, it is assumed that a job that is finished before its departure date or arrives at the customer before its due date will incur a stage-dependent corresponding inventory cost (WIP inventory, finished-good inventory or customer inventory cost). The objective is to find a coordinated production and delivery schedule such that the sum of setup, delivery and inventory costs is minimised. We formulate the problem as a nonlinear model in a general way and provide some properties. We then derive a precise instance from the general model and develop a heuristic algorithm for solving this precise instance. In order to evaluate the performance of the heuristic algorithm, we propose a simple branch-and-bound (B&B) approach for small-size problems, and a lower bound based on the Lagrangian relaxation method for large-size problems. Computational experiments show that the heuristic algorithm performs well on randomly generated problems.

Keywords:

• scheduling
• operational research
• flow shop scheduling
• batch
• production and transportation
• Lagrangian relaxation

Acknowledgements

The authors would like to thank the two anonymous reviewers of this paper for their helpful comments and suggestions that have improved the quality of the paper.