Minimizing total inventory cost on a single machine in just-in-time manufacturing

The just-in-time concept decrees not to accept ordered goods before their due dates in order to avoid inventory cost. This bounces the inventory cost back to the manufacturer: products that are completed before their due dates have to be stored. Reducing this type of storage cost by preclusion of early completion conflicts with the traditional policy of keeping work-in-process inventories down. This paper addresses a single-machine scheduling problem with the objective of minimizing total inventory cost, comprising cost associated with work-in-process inventories and storage cost as a result of early completion. The cost components are measured by the sum of the job completion times and the sum of the job earlinesses. This problem differs from more traditional scheduling problems, since the insertion of machine idle time may reduce total cost. The search for an optimal schedule, however, can be limited to the set of job sequences, since for any sequence there is a clear-cut way to insert machine idle time in order to minimize total inventory cost. We apply branch-and-bound to identify an optimal schedule. We present five approaches for lower bound calculation, based upon relaxation of the objective function, of the state space, and upon Lagrangian relaxation.