A GRASP+VND algorithm for a class of job scheduling problem in parallel machines

  • Dalessandro Soares Vianna Universidade Federal Fluminense
  • Sandra Regina Coelho Universidade Candido Mendes - Campos
  • Marcilene de Fátima Dianin Vianna Universidade Estadual Norte Fluminense
Keywords: Job Scheduling Problem in Parallel Machines, GRASP, VND, Combinatorial Optimization, Petrobras


Petróleo Brasileiro S/A (Petrobras) is the biggest Brazilian company in energy business. It acts in exploration, production, refinement, commercialization and transport of petroleum by products in Brazil and other countries. Most of the petroleum production is concentrated in the Campos basin, where the company port (port of Imbetiba – Macaé/RJ) is located. All the oil rigs supply is done using this port. Researches made at the port of Imbetiba show the need of optimizing, among others, the problem of towboat scheduling. In this problem, the order of towboat attendance must be decided and, according to the material that each one carry, the following restrictions must be respected: each towboat has a subset of piers where it can be attended; each one has a attendance priority; and each one has a minimal time where it can be attended, that is, before this time it cannot be attended. This paper proposes a GRASP algorithm for the problem of towboat scheduling, which utilizes the technique VND as local search. Three neighborhood structures are used: Exchange, Interchange and Relocation. Computational results show that the proposed algorithm is efficient when compared with traditional GRASP algorithms.
How to Cite
Vianna, D., Coelho, S., & Vianna, M. (2010). A GRASP+VND algorithm for a class of job scheduling problem in parallel machines. Brazilian Journal of Operations & Production Management, 7(2), 63-80. Retrieved from https://bjopm.emnuvens.com.br/bjopm/article/view/V7N2A4_

Most read articles by the same author(s)