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. NOTE: For jobs that don't have a deadline tardiness is intended as undefined; and since the penalty is tardiness * importance, the penalty of jobs without a deadline is undefined as well.
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.
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.
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:
- 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.
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
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
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
A given input is:
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).
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).
Additional sample instances: download
Notes and Updates
Note that the notion of end time is not explicitly defined: we assume the value of the end time E as traditionally set to E=S+L, where 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: Marcello Balduccini
- Affiliation: Kodak Research Laboratories
- Author: Yuliya Lierler
- Affiliation: University of Kentucky