title   
  

Operational variable job scheduling with eligibility constraints: a randomized constraint-graph-based approach

Eliiyi, Deniz Türsel and Korkmaz, Aslıhan Gizem and Çiçek, Ercüment Abdullah (2009) Operational variable job scheduling with eligibility constraints: a randomized constraint-graph-based approach. Technological and Economic Development of Economy, 15 (2). pp. 245-266. ISSN 1392-8619 (print) 1822-3613 (online)

Full text not available from this repository.

Official URL: http://dx.doi.org/10.3846/1392-8619.2009.15.245-266

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 Lime 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 ties 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.

Item Type:Article
Uncontrolled Keywords:operational variable job scheduling; eligibility constraints; optimal berth allocation; genetic algorithm; constraint satisfaction; constraint graph
Subjects:UNSPECIFIED
ID Code:13672
Deposited By:Ercüment Abdullah Çiçek
Deposited On:13 Jan 2010 21:15
Last Modified:25 May 2011 14:12

Repository Staff Only: item control page