skip to main content
Idioma:

Efficient heuristics for the parallel blocking flow shop scheduling problem

Ribas, Imma ; Companys, Ramon ; Tort-Martorell, Xavier

Expert systems with applications, 2017-05, Vol.74, p.41-54 [Periódico revisado por pares]

New York: Elsevier Ltd

Texto completo disponível

Citações Citado por
  • Título:
    Efficient heuristics for the parallel blocking flow shop scheduling problem
  • Autor: Ribas, Imma ; Companys, Ramon ; Tort-Martorell, Xavier
  • Assuntos: Blocking flow shop ; Completion time ; Control ; Distributed permutation flow shop ; Economia i organització d'empreses ; Greedy algorithms ; Heuristic ; Heuristic algorithms ; Heurística ; Investigació operativa ; Job shop scheduling ; Machine shops ; Mathematical models ; Mathematical optimization ; Operations research ; Optimització matemàtica ; Parallel flow ; Parallel flow shop ; Producció ; Scheduling ; Scheduling algorithms ; Studies ; Àrees temàtiques de la UPC
  • É parte de: Expert systems with applications, 2017-05, Vol.74, p.41-54
  • Descrição: •New Constructive heuristic for both the PBFSP and the DBFSP.•Combination of IGA and ILS methods with two types of VNS.•A MILP model solved for small-sized instances.•The proposed methods are very effective. We consider the NP-hard problem of scheduling n jobs in F identical parallel flow shops, each consisting of a series of m machines, and doing so with a blocking constraint. The applied criterion is to minimize the makespan, i.e., the maximum completion time of all the jobs in F flow shops (lines). The Parallel Flow Shop Scheduling Problem (PFSP) is conceptually similar to another problem known in the literature as the Distributed Permutation Flow Shop Scheduling Problem (DPFSP), which allows modeling the scheduling process in companies with more than one factory, each factory with a flow shop configuration. Therefore, the proposed methods can solve the scheduling problem under the blocking constraint in both situations, which, to the best of our knowledge, has not been studied previously. In this paper, we propose a mathematical model along with some constructive and improvement heuristics to solve the parallel blocking flow shop problem (PBFSP) and thus minimize the maximum completion time among lines. The proposed constructive procedures use two approaches that are totally different from those proposed in the literature. These methods are used as initial solution procedures of an iterated local search (ILS) and an iterated greedy algorithm (IGA), both of which are combined with a variable neighborhood search (VNS). The proposed constructive procedure and the improved methods take into account the characteristics of the problem. The computational evaluation demonstrates that both of them –especially the IGA– perform considerably better than those algorithms adapted from the DPFSP literature.
  • Editor: New York: Elsevier Ltd
  • Idioma: Inglês
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.