welcome: please sign in
location: FinalProblemDescriptions / IncrementalScheduling

Incremental Scheduling

Problem Description

In this domain, a reasoner keeps a schedule updated with respect to the addition of jobs and to equipment going offline.

All numerical quantities discussed below are integers. The largest possible value is specified by relation max_value(mv).

List of devices

Each device has one or more identical instances. Each instance may be offline, meaning that it cannot be used for scheduling.

List of jobs

For each job, the following are specified:

A job is tardy if it is completed after its deadline. Its tardiness is computed as the difference between the job's actual end time and its deadline. The penalty for a job being tardy is computed as td * imp, where td is the job's tardiness and imp is the job's importance.

Maximum total penalty

The total penalty of a schedule is the sum of the penalties of the single jobs. Schedules with a higher total penalty greater than the specified maximum total penalty are not valid solutions.

Current schedule

The current schedule, which must be updated by the scheduler, specifies, FOR A SUBSET OF THE AVAILABLE JOBS, each job's start time and the device instance the job must be run on. Intuitively, elements of the list of jobs (see section above) that have no start time and device instance assigned in the current schedule should be viewed as jobs that have been added after the current schedule was computed.

Current time

The current time ct is an integer specifying at which point the execution of the schedule is. Jobs whose end time is smaller than OR EQUAL TO ct are expected to have already been completed.

The scheduling task

Given the list of devices, the list of jobs, the current schedule, and the current time, the scheduler is expected to find a new schedule such that:

Rescheduling a job

Whenever a job needs to be re-scheduled after it has already started, the scheduler will need to re-schedule the complete job, i.e. it will discard the part of the job that has already performed. The output of the scheduler should indicate that the job has been re-scheduled.

Predicates

    importance/2, precedes/2, max_total_penalty/1, curr_job_start/2, curr_on_instance/2, curr_time/1

Input format

max_value(<mv>): maximum possible value for the numerical quantities

device(<d>): d is a device
instances(<d>,<n>): device d has n instances
offline_instance(<d>,<i>): instance 1 <= i <= n is offline

job(<j>): j is a job
job_device(<j>,<d>): j must be executed by device d
job_len(<j>,<l>): the amount of time needed to perform j is l, where l is an integer
deadline(<j>,<dl>): the deadline of j is dl
importance(<j>,<imp>): the importance of j is imp >= 1
precedes(<j1>,<j2>): the end time of j1 must precede (be less than or equal to) the start time of j2

max_total_penalty(<mp>): the total penalty of the schedule must be less than or equal to mp.

curr_job_start(<j>,<st>): the start time of j in the current schedule is st
curr_on_instance(<j>,<i>): in the current schedule, j is scheduled to run on device instance i

curr_time(<ct>): the current time is ct

Output format

start(<j>,<t>): the execution of job j will start at time t
on_instance(<j>,<i>): job j will be executed on instance i
penalty(<j>,<p>): the penalty of job j is p
tot_penalty(<tp>): the total penalty of the schedule is tp
rescheduled(<j>): job j has been re-scheduled after execution had already started

Example(s)

INPUT:

max_value(20).
device(d1). instances(d1,1).
device(d2). instances(d2,2).
offline_instance(d2,1).
%
job(j1). job_device(j1,d1). job_len(j1,4).
job(j2). job_device(j2,d2). job_len(j2,5). deadline(j2,10). importance(j2,1).
precedes(j1,j2).
job(j3). job_device(j3,d2). job_len(j3,4). deadline(j3,12). importance(j3,2).
%
max_total_penalty(3).
%
curr_job_start(j1,0). curr_on_instance(j1,1).
curr_job_start(j2,4). curr_on_instance(j2,1).
%
curr_time(2).

OUTPUT:

start(j1,0).
on_instance(j1,1).
%
start(j2,7).
on_instance(j2,2).
penalty(j2,2).
%
start(j3,2).
on_instance(j3,2).
penalty(j3,0).
%
tot_penalty(2).

Notes and Updates

S is the start time and L is the length (aka duration). So, if the start time is 2 and the length is 5, the end time is 7. "End time" intuitively means that the jobs has been completed by that time, and thus is ready.

Author(s)

ASP Competition 2011: FinalProblemDescriptions/IncrementalScheduling (last edited 2011-03-09 18:30:59 by GiovambattistaIanni)