Operations and Shipment Scheduling of a Batch on a Flexible Machine

We consider processing and shipment scheduling of a batch of size M jobs on a flexible (multifunctional) machine. All jobs in the batch require the same sequence ofNoperations on the machine. Costs are incurred in the forms of holding costs of jobs waiting for the next operation, setup costs whenever the machine is set up for a new operation, and shipment cost whenever the whole batch or a part of it is shipped to the customer. Using a dynamic programming formulation of the problem, we first show how the problem size increases inMandN. Then, by focusing on the properties of some classes of batch-splitting policies, a heuristic algorithm is presented that generates suboptimal policies. Some numerical results are provided which show that the algorithm performs very well.