Operational variable job scheduling with eligibility constraints: A randomized constraint‐graph‐based approach

Abstract

In this study, we consider the problem of Operational Variable Job Scheduling, also referred to as parallel machine scheduling with time windows. The problem is a more general version of the Fixed Job Scheduling problem, involving a time window for each job larger than its processing time. The objective is to find the optimal subset of the jobs that can be processed. An interesting application area lies in Optimal Berth Allocation, which involves the assignment of vessels arriving at the port to appropriate berths within their time windows, while maximizing the total profit from the served vessels. Eligibility constraints are also taken into consideration. We develop an integer programming model for the problem. We show that the problem is NP‐hard, and develop a constraint‐graph‐based construction algorithm for generating near‐optimal solutions. We use genetic algorithm and other improvement algorithms to enhance the solution. Computational experimentation reveals that our algorithm generates very high quality solutions in very small computation times.

Santrauka

Nagrinejama nepastoviu darbu planavimo problema, susijusi su mašinu darbo planavimu laiko tarpais. Ši problema yra bendresne fiksuotu darbu planavimo problemos versija, kai laiko tarpai ilgesni už darbu trukme. Siekiama rasti optimalu atliekamu darbu poaibi. Geras pavyzdys yra optimali laivu priežiūra prieplaukoje, kai laivai prisišvartuoja laiko tarpais, taip maksimizuodami iš laivu gaunama pelna. Taip pat ivertinami tinkamumo ribojimai. Problemai spresti sukurtas sveikuju skaičiu programavimo modelis. Sukurtas apribojimu ir kreiviu pavidalo algoritmas, gebantis generuoti apytikslius sprendinius. Jiems patikslinti naudojamas genetinis algoritmas ir kiti korekciniai algoritmai. Kompiuteriniai eksperimentai atskleide, kad sukurtieji algoritmai generuoja labai tikslius sprendinius per labai trumpa laiko tarpa.

Keywords:

• operational variable job scheduling
• eligibility constraints
• optimal berth allocation
• genetic algorithm
• constraint satisfaction
• constraint graph

Reikšminiai žodžiai:

• kintamos trukmes darbu planavimas
• tinkamumo ribojimai
• optimali laivu priežiūra
• genetinis algoritmas
• apribojimu išpildymas
• apribojimu kreive