A Multi-Exchange Neighborhood Search Heuristic for an Integrated Clustering and Machine Setup Model for PCB Manufacturing
In the manufacture of printed circuit boards, electronic components are attached to a blank board by one or more pick-and-place machines. Frequent machine setups, though time consuming, can reduce overall processing time. We consider the Integrated Clustering and Machine Setup (ICMS) model, which in...
| Main Authors: | , , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5208 |
| _version_ | 1811087353168527360 |
|---|---|
| author | Magazine, Michael J. Polak, George G. Sharma, Dushyant |
| author_facet | Magazine, Michael J. Polak, George G. Sharma, Dushyant |
| author_sort | Magazine, Michael J. |
| collection | MIT |
| description | In the manufacture of printed circuit boards, electronic components are attached to a blank board by one or more pick-and-place machines. Frequent machine setups, though time consuming, can reduce overall processing time. We consider the Integrated Clustering and Machine Setup (ICMS) model, which incorporates this tradeoff between processing time and setup time and seeks to minimize the sum of the two. Solving this model to optimality is intractable for very large-scale instances. We show that ICMS is NP-hard and consequently propose and test a heuristic based on multi-exchange neighborhood search structures. Initial numerical results are very encouraging. Keywords: Printed circuit board assembly, feeder slot assignment, product clustering, integer programming, computational complexity, heuristics. |
| first_indexed | 2024-09-23T13:44:44Z |
| format | Working Paper |
| id | mit-1721.1/5208 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:44:44Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/52082019-04-10T15:18:11Z A Multi-Exchange Neighborhood Search Heuristic for an Integrated Clustering and Machine Setup Model for PCB Manufacturing Magazine, Michael J. Polak, George G. Sharma, Dushyant In the manufacture of printed circuit boards, electronic components are attached to a blank board by one or more pick-and-place machines. Frequent machine setups, though time consuming, can reduce overall processing time. We consider the Integrated Clustering and Machine Setup (ICMS) model, which incorporates this tradeoff between processing time and setup time and seeks to minimize the sum of the two. Solving this model to optimality is intractable for very large-scale instances. We show that ICMS is NP-hard and consequently propose and test a heuristic based on multi-exchange neighborhood search structures. Initial numerical results are very encouraging. Keywords: Printed circuit board assembly, feeder slot assignment, product clustering, integer programming, computational complexity, heuristics. 2004-05-28T19:28:08Z 2004-05-28T19:28:08Z 2001-03 Working Paper http://hdl.handle.net/1721.1/5208 en_US Operations Research Center Working Paper;OR 352-01 1946141 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Magazine, Michael J. Polak, George G. Sharma, Dushyant A Multi-Exchange Neighborhood Search Heuristic for an Integrated Clustering and Machine Setup Model for PCB Manufacturing |
| title | A Multi-Exchange Neighborhood Search Heuristic for an Integrated Clustering and Machine Setup Model for PCB Manufacturing |
| title_full | A Multi-Exchange Neighborhood Search Heuristic for an Integrated Clustering and Machine Setup Model for PCB Manufacturing |
| title_fullStr | A Multi-Exchange Neighborhood Search Heuristic for an Integrated Clustering and Machine Setup Model for PCB Manufacturing |
| title_full_unstemmed | A Multi-Exchange Neighborhood Search Heuristic for an Integrated Clustering and Machine Setup Model for PCB Manufacturing |
| title_short | A Multi-Exchange Neighborhood Search Heuristic for an Integrated Clustering and Machine Setup Model for PCB Manufacturing |
| title_sort | multi exchange neighborhood search heuristic for an integrated clustering and machine setup model for pcb manufacturing |
| url | http://hdl.handle.net/1721.1/5208 |
| work_keys_str_mv | AT magazinemichaelj amultiexchangeneighborhoodsearchheuristicforanintegratedclusteringandmachinesetupmodelforpcbmanufacturing AT polakgeorgeg amultiexchangeneighborhoodsearchheuristicforanintegratedclusteringandmachinesetupmodelforpcbmanufacturing AT sharmadushyant amultiexchangeneighborhoodsearchheuristicforanintegratedclusteringandmachinesetupmodelforpcbmanufacturing AT magazinemichaelj multiexchangeneighborhoodsearchheuristicforanintegratedclusteringandmachinesetupmodelforpcbmanufacturing AT polakgeorgeg multiexchangeneighborhoodsearchheuristicforanintegratedclusteringandmachinesetupmodelforpcbmanufacturing AT sharmadushyant multiexchangeneighborhoodsearchheuristicforanintegratedclusteringandmachinesetupmodelforpcbmanufacturing |