A branch‐and‐price algorithm for the general case of scheduling parallel machines with a single server

A branch‐and‐price algorithm for the general case of scheduling parallel machines with a single server

0.00 Avg rating0 Votes
Article ID: iaor20121292
Volume: 39
Issue: 9
Start Page Number: 2242
End Page Number: 2247
Publication Date: Sep 2012
Journal: Computers and Operations Research
Authors: , ,
Keywords: combinatorial optimization
Abstract:

We consider the strongly NP‐hard problem of scheduling two‐operation non‐preemptable jobs on two identical parallel machines. A single server, that can handle at most one job at a time, is available to carry out the first (or setup) operation. The second operation, to be carried out on the same machine but without the server, must be executed immediately after the setup. The objective is to minimize the makespan. We apply a column generation method to a population of partial schedules, in turn generated by some well known heuristics, to achieve effective and efficient solutions. We compare the performance of this method with those proposed earlier and also suggest future work.

Reviews

Required fields are marked *. Your email address will not be published.