Optimization of resource-constrained project schedules by simulated annealing and variable neighborhood search

Abstract

Applications of information technologies are often related to making some schedules, timetables of tasks or jobs with constrained resources. In this paper we consider job scheduling and optimization algorithms related to resources, time and other constraints. Schedule optimization procedures, based on schedule coding by priority list of jobs, are created and investigated. Optimal priority list of jobs is found by approaching algorithms of local and global search, namely, random search and simulated annealing methods with the variable neighborhood, defined by the decoding procedure applied. Computational results with testing data from project scheduling Library are given.

Taikant informacines technologijas dažnai susiduriama su įvairiomis darbų ar užduočių tvarkaraščių sudarymo problemomis, kai ištekliai, reikalingi užduotims atlikti, yra riboti. Šiame straipsnyje yra nagrinėjami darbų tvarkaraščių sudarymo ir optimizavimo algoritmai, atsižvelgiant į išteklių, laiko bei kitokius ribojimus. Sukurtos ir tiriamos tvarkaraščio optimizavimo procedūros, paremtos tvarkaraščio kodavimu pagal darbų pirmumo sąrašą. Optimalus darbų pirmumo sąrašas randamas derinant lokaliosios ir globaliosios paieškos algoritmus – atsitiktinės paieškos ir modeliuojamojo atkaitinimo metodus su kintama aplinka. Pateikti skaičiavimo rezultatai, naudojant testų duomenis iš tvarkaraščių sudarymo uždavinių bibliotekos.