Scheduling policies in the M/G/1 make-to-stock queue

Abstract

In this paper, we analyse a production/inventory system modelled as an M/G/1 make-to-stock queue producing different products requiring different and general production times. We study different scheduling policies including the static first-come-first-served, preemptive and non-preemptive priority disciplines. For each static policy, we exploit the distributional Little's law to obtain the steady-state distribution of the number of customers in the system and then find the optimal inventory control policy and the cost. We additionally provide the conditions under which it is optimal to produce a product according to a make-to-order policy. We further extend the application area of a well-known dynamic scheduling heuristic, Myopic(T), for systems with non-exponential service times by permitting preemption. We compare the performance of the preemptive-Myopic(T) heuristic alongside that of the static preemptive-bμ rule against the optimal solution. The numerical study we have conducted demonstrates that the preemptive-Myopic(T) policy is superior between the two and yields costs very close to the optimal.

Keywords:

• make-to-stock
• M/G/1 queue
• Little's distributional law
• static and dynamic production scheduling
• inventory control

Acknowledgements

We thank Professor Martin Puterman whose help has been invaluable for us while implementing the value iteration algorithm to obtain the optimal solutions. We are thankful to the two anonymous referees whose suggestions have significantly improved the presentation of the paper. This work was supported in part by Natural Sciences and Engineering Research Council (NSERC) of Canada.