Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times

详细信息    查看全文

• 作者：Pedro Leite Rocha ; Martí ; n Gó ; mez Ravetti ; Geraldo Robson Mateus ; Panos M. Pardalos
• 关键词：Scheduling ; GRASP ; Branch-and-bound ; Sequence-dependent setups ; Machine-dependent setups ; Parallel machines
• 刊名：Computers and Operations Research
• 出版年：2008
• 出版时间：April 2008
• 年：2008
• 卷：35
• 期：4
• 页码：1250-1264
• 全文大小：249 K

文摘

A scheduling problem with unrelated parallel machines, sequence and machine-dependent setup times, due dates and weighted jobs is considered in this work. A branch-and-bound algorithm (B&B) is developed and a solution provided by the metaheuristic GRASP is used as an upper bound. We also propose a set of instances for this type of problem. The results are compared to the solutions provided by two mixed integer programming models (MIP) with the solver CPLEX 9.0. We carry out computational experiments and the algorithm performs extremely well on instances with up to 30 jobs.