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:

• - Job's device, i.e. which device should be used for the job (REQUIRED). - Length, i.e. how long production of the job will take (REQUIRED). - Deadline, i.e. the job's latest end time (OPTIONAL).

  - Importance: an integer imp >= 1 (OPTIONAL, DEFAULTS TO 1). - A list of jobs that precede it, i.e. must be completely executed before the current job can start.

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 ct are expected to have already been completed, while jobs whose start time is greater than or equal to ct are yet to be started.

[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:

• the start time and allocated instance of a job that has already been completed remain the same;
• the start time and allocated instance of a job that is currently being executed on a device instance which is online remain the same;
• jobs whose expected end time is greater than the current time cannot be scheduled on a device instance that is offline;
• precedences between jobs are respected;
• the total penalty is no larger than the maximum total penalty.

[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

• Input: max_value/1, device/1, instances/2, offline_instance/2, job/1, job_device/2, job_len/2, deadline/2,

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

• Output: start/1, on_instance/2, penalty/2, tot_penalty/1, rescheduled/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

• Specification: updated on date 28/01/2011;

Author(s)

• Author: Marcello Balduccini
  • Affiliation: Kodak Research Laboratories
• Author: Yuliya Lierler
  • Affiliation: University of Kentucky, USA