Dissertation Presentation :: Batch Scheduling of Two-machine Flowshop: An Application in PCB Assembly

Primary tabs

This research investigates the batch scheduling problem of two-machine limited-buffer flowshop with setup and removal times considered. Our problem arises in the electronic assembly industry. We consider a printed circuit board (PCB) assembly line that has two different placement machines. One of them places commonly used components, such as resistors and capacitors, at high speed. The other one is more flexible but at a lower speed. Large chips and other irregular components are placed on this machine. Two placement machines are connected by a high-speed synchronized conveyor, which is equivalent to a buffer with limited capacity. Sequence-independent setup and removal times are required for each batch being processed on a machine. Our objective is to find the sequence of jobs on the machines of the production line such that the overall completion time is minimized. In this dissertation, we present that, under the steady state condition, the batch scheduling problem can be converted to a special structured traveling salesman problem (TSP), which can be optimally solved in time. Then we develop two approximation algorithms, both of which provide lower bounds of the optimal solution. A branch and bound algorithm is developed to find an optimal solution for any general cases. Finally various numerical experiments show the effectiveness of our approaches.


  • Workflow Status: Published
  • Created By: Barbara Christopher
  • Created: 10/08/2010
  • Modified By: Fletcher Moore
  • Modified: 10/07/2016


No keywords were submitted.

Target Audience

No target audience selected.