Batch scheduling of two-machine limited-buffer flowshop with setup and removal times.

摘要

This research investigates the batch scheduling problem for a two-machine limited-buffer flowshop with setup and removal times considered. Our objective is to find the sequence of jobs on the machines such that the overall completion time is minimized. We show that under the steady state conditions, the batch scheduling problem can be converted to a special structured traveling salesman problem (TSP) that can be optimally solved in O( n log n) time. We develop two approximation algorithms, both of which provide lower bounds for the value of the optimal solution. A branch and bound algorithm is developed to find an optimal solution for the general case. We also perform a case study for a specific electronic assembly application. Finally, various numerical experiments show the effectiveness of our algorithms.