Biblioteca Digital do Instituto Politécnico de Bragança   Instituto Politécnico de Bragança

Biblioteca Digital do IPB >
Escola Superior de Tecnologia e Gestão >
Gestão Industrial >
DGI - Publicações em Proceedings Indexadas ao ISI/Scopus >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10198/2670

Título: Solving a multiprocessor problem by column generation and branch-and-price
Autor: Duarte, António J.S.T.
Carvalho, J.M. Valério
Palavras-chave: Scheduling
Branch-and-price
Issue Date: 2010
Citação: Duarte, António J.S.T. ; Valério de Valério, J. M. ; (2010) - Solving a multiprocessor problem by column generation and branch-and-price. In IFAC MCPL. Coimbra.
Resumo: This work presents an algorithm for solving exactly a scheduling problem with identical parallel machines and malleable tasks, subject to arbitrary release dates and due dates. The objective is to minimize a function of late work and setup costs. A task is malleable if we can freely change the set of machines assigned to its processing over the time horizon. We present an integer programming model, a Dantzig-Wolfe decomposition reformulation and its solution by column generation. We also developed an equivalent network flow model, used for the branching phase. Finally, we carried out extensive computational tests to verify the algorithm’s efficiency and to determine the model’s sensitivity to instance size parameters: the number of machines, the number of tasks and the size of the planning horizon.
URI: http://hdl.handle.net/10198/2670
Appears in Collections:DGI - Publicações em Proceedings Indexadas ao ISI/Scopus

Files in This Item:

File Description SizeFormat
mcpl2010Definitivo.pdf171 kBAdobe PDFView/Open

Please give feedback about this item
Statistics
FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Logotipo do DeGóis 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 


© Instituto Politécnico de Bragança - Biblioteca Digital - Feedback - Statistics
Promotores do RCAAP   Financiadores do RCAAP

Fundação para a Ciência e a Tecnologia Universidade do Minho   Governo Português Ministério da Educação e Ciência PO Sociedade do Conhecimento (POSC) Portal oficial da União Europeia