Heuristic Algorithms to Maximize Revenue and the Number of Jobs Processed on Parallel Machines

• A set of jobs has to be processed on parallel machines. For each job, there are given a release time and a due date and the job must be processed no later than its due date. If the job will be completed no later than the given due date, a benefit will be earned. Otherwise, this job will be rejected and the benefit will be discarded. The criterion under consideration is to maximize the weighted sum of the benefits and the number of jobs processed in time. Some properties of the objective function are found which allow to construct a optimal schedule. We develop a simulated annealing algorithm, a tabu search algorithm, and a genetic algorithm for solving this problem. The developed algorithms were tested on moderate and large instances with up to 500 jobs and 50 machines. Some recommendations are given showing how to use the obtained results and developed algorithms in production planning.

Subject headings

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Keyword

scheduling

uniform machines

revenue maximization

genetic algorithm

simulated annealing

tabu search

Publication and Content Type

ref (subject category)

art (subject category)