A job completion time estimation method for work center scheduling

Two related issues in the development of scheduling algorithms are addressed. The first centers on the inability of schedulers to predict when jobs will actually be completed. Existing jobs scheduled without information concerning future arrivals are frequently postponed to make room for incoming jobs of significant urgency. A probabilistic method of considering future arrivals when scheduling a bottleneck work center via the Lagrangian relaxation method is presented. In addition, a method of reducing the scheduling time step is presented. Implementation of a smaller time step allows for more accurate representation of job processing times. Both methods are combined to improve the determination of promised delivery dates