Sequencing jobs for an automated manufacturing module with buffer

This article deals with the real-time scheduling of jobs for an automated manufacturing module offering a variety of operations with negligible setup times. Since the jobs are brought to the system by a paced line at a fixed rate, each job is expected to be processed within a fixed cycle time. Hence, a group of jobs with longer processing-time may cause immediate accumulation of jobs in the limited input buffer. Consequently, an arriving job may be blocked from entering until the job in the station is completed. A Dynamic Program is implemented to schedule the jobs with the minimum total blocking time. Depending on the data, this implementation may become computationally intractable, and thereby, a heuristic is developed to produce good solutions in polynomial time. The worst case error bounds are established for the heuristic solutions. An extensive experimentation shows that the heuristic yields close to optimal solutions effectively.