A GRASP+VND algorithm for a class of job scheduling problem in parallel machines
AbstractPetró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.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors must have a written permission from any third-party materials used in the article, such as figures and graphics. The permission must explicitly allow authors to use the materials. The permission should be submitted with the article, as a supplementary file.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after BJO&PM publishes it (See The Effect of Open Access).