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 each job's start time and the device instance the job must be run on.

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

Input format

max_value(<mv>): maximum possible value of 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

eq(st(<d>,<j>),<t>): the execution of job j on device d will start at time t

eq(on_instance(<j>),<i>): job j will be executed on instance i

eq(pen(<j>),<p>): the penalty of job j is p

eq(tot_pen,<tp>): the total penalty of the schedule is tp

rescheduled(<j>): job j has been re-scheduled after execution had already started

Example

INPUT: max_value(20). device(d1). instance(d1,1). device(d2). instance(d2,2). offline(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: eq(st(d1,j1),0). eq(on_instance(j1),1). eq(pen(j1),0). % eq(st(d2,j2),6). eq(on_instance(j2),2). eq(pen(j2),1). rescheduled(j2). % eq(st(d2,j3),2). eq(on_instance(j3),2). eq(pen(j3),0). % eq(tot_pen,1).

Author(s)

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