# US 2006/0218551 A1 · Jobstream planner considering network contention & resource availability

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2006/0218551 A1
- Document ID: US20060218551A1
- Status: Published application
- Kind: A1
- Application number: 11/086,716
- Filed: 2005-03-22
- Published: 2006-09-28
- Earliest claimed: 2005-03-22
- Assignees: International Business Machines Corporation
- Inventors: Viktors Berstis; Kyle Boon; Creighton Hicks; Bella Voldman
- Web page: https://patentgrep.com/patent/US20060218551A1

## CPC

- G06F 9/5038: {considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups)}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/5072: {Grid computing}
- G06F 2209/483: Multiproc
- G06F 2209/5021: Priority
- G06F 2209/506: Constraint
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Disclosed is a computer-implemented planning process that aids a system administrator in the task of creating a job schedule. The process treats enterprise computing resources as a grid of resources, which provides greater flexibility in assigning resources to jobs. During the planning process, an administrator or other user, or software, builds a job-dependency tree. Jobs are then ranked according to priority, pickiness, and network centricity. Difficult and problematic jobs then are assigned resources and scheduled first, with less difficult jobs assigned resources and scheduled afterwards. The resources assigned to the most problematic jobs then are changed iteratively to determine if the plan improves. This iterative approach not only increases the efficiency of the original job schedule, but also allows the planning process to react and adapt to new, ad-hoc jobs, as well as unexpected interruptions in resource availability.

## Claims

### Claim 1

A computer-implemented planning process for scheduling multiple jobs in a digital data processing system while considering network and processing resources in the digital data processing system, the planning process comprising:
steps for building a job-dependency tree;
steps for ranking each job;
steps for assigning processing resources to each job;
steps for scheduling each job so that each job executes by a user-requested time; and
steps for optimizing the schedule of jobs.

### Claim 2 (depends on 1)

The process of claim 1 wherein the steps for ranking each job comprise:
steps for identifying all plannable jobs;
steps for calculating the pickiness of each plannable job;
steps for calculating the network centricity of each plannable job; and
steps for calculating a job rank for each job, where each job's rank is equal to the sum of the job's priority, pickiness, and network centricity.

### Claim 3

A computer-implemented planning process for scheduling multiple jobs in a digital data processing system while considering network and processing resources in the digital data processing system, wherein each job has a user-assigned priority, the planning process comprising:
building a dependency tree;
identifying all plannable jobs;
calculating the pickiness of each plannable job;
calculating the network centricity of each plannable job;
calculating a job rank for each job, where each job's rank is equal to the sum of the job's priority, pickiness, and network centricity; and
assigning resources to the job with the highest job rank.

### Claim 4 (depends on 3)

The process of claim 3 wherein the step of calculating a plannable job's pickiness comprises the steps of:
estimating the job's runtime;
determining the job's time frame;
determining the number of machines in the digital data processing system that have sufficient capacity to execute the job within the job's time frame; and
dividing the number of machines that have sufficient capacity by the total number of machines in the digital data processing system.

### Claim 5 (depends on 3)

The process of claim 3 wherein the step of calculating a plannable job's network centricity comprises the steps of:
determining the preferred path between each pair of machines in the digital data processing system;
determining the maximum bandwidth of each preferred path;
determining the tick value of each preferred path;
identifying each machine that could execute the job;
calculating the data transfer time between each machine that could execute the job and any remote machine with which the job must exchange data;
multiplying the result of the previous step by the maximum tick value of any preferred path; and
averaging the result of the previous step for all machines that could execute the job.

### Claim 6 (depends on 3)

The process of claim 3 wherein the step of assigning resources to the job with the highest rank comprises:
calculating the job's total execution time on each machine that could execute the job; adding the job's total execution time on each machine that could execute the job and the job's network centricity; and
assigning the job to the machine on which the previous step produces the highest value.

### Claim 7 (depends on 3)

The process of claim 3 further comprising the steps of:
repeating each step until all jobs are scheduled and resources are assigned to all jobs; evaluating the schedule's fitness;
switching resources assigned to a first job and a second job;
re-evaluating the schedule's fitness with the resources switched; and
comparing the schedule's fitness with the resources switched and the schedule's fitness before switching resources; and
retaining the assignment of resources that produces the best schedule fitness.

### Claim 8 (depends on 4)

The process of claim 4 further comprising the steps of: repeating each step until all jobs are scheduled and resources are assigned to all jobs;
evaluating the schedule's fitness;
switching resources assigned to a first job and a second job;
re-evaluating the schedule's fitness with the resources switched; and
comparing the schedule's fitness with the resources switched and the schedule's fitness before switching resources; and
retaining the assignment of resources that produces the best schedule fitness.

### Claim 9 (depends on 5)

The process of claim 5 further comprising the steps of:
repeating each step until all jobs are scheduled and resources are assigned to all jobs;
evaluating the schedule's fitness;
switching resources assigned to a first job and a second job;
re-evaluating the schedule's fitness with the resources switched; and
comparing the schedule's fitness with the resources switched and the schedule's fitness before switching resources; and
retaining the assignment of resources that produces the best schedule fitness.

### Claim 10 (depends on 6)

The process of claim 6 further comprising the steps of:
repeating each step until all jobs are scheduled and resources are assigned to all jobs;
evaluating the schedule's fitness;
switching resources assigned to a first job and a second job;
re-evaluating the schedule's fitness with the resources switched; and
comparing the schedule's fitness with the resources switched and the schedule's fitness before switching resources; and
retaining the assignment of resources that produces the best schedule fitness.

### Claim 11 (depends on 7)

The process of claim 7 wherein the steps of evaluating and re-evaluating the schedule's fitness comprise evaluating each job's fitness, and evaluating each job's fitness comprises the steps of:
assigning an initial value to the job's fitness;
multiplying the job's priority by a user-specified weight and subtracting the resulting product from the initial value;
adding a value to the resulting product that is proportional to the time between the predicted end of the job's execution and the job's deadline; and
subtracting a value from the resulting sum that is proportional to the tick value of the preferred path between the machine assigned to execute the job and any remote machine with which the job must exchange data.

### Claim 12 (depends on 8)

The process of claim 8 wherein the steps of evaluating and re-evaluating the schedule's fitness comprise evaluating each job's fitness, and evaluating each job's fitness comprises the steps of:
assigning an initial value to the job's fitness;
multiplying the job's priority by a user-specified weight and subtracting the resulting product from the initial value;
adding a value to the resulting product that is proportional to the time between the predicted end of the job's execution and the job's deadline; and
subtracting a value from the resulting sum that is proportional to the tick value of the preferred path between the machine assigned to execute the job and any remote machine with which the job must exchange data.

### Claim 13 (depends on 9)

The process of claim 9 wherein the steps of evaluating and re-evaluating the schedule's fitness comprise evaluating each job's fitness, and evaluating each job's fitness comprises the steps of:
assigning an initial value to the job's fitness;
multiplying the job's priority by a user-specified weight and subtracting the resulting product from the initial value;
adding a value to the resulting product that is proportional to the time between the predicted end of the job's execution and the job's deadline; and
subtracting a value from the resulting sum that is proportional to the tick value of the preferred path between the machine assigned to execute the job and any remote machine with which the job must exchange data.

### Claim 14 (depends on 10)

The process of claim 10 wherein the steps of evaluating and re-evaluating the schedule's fitness comprise evaluating each job's fitness, and evaluating each job's fitness comprises the steps of:
assigning an initial value to the job's fitness;
multiplying the job's priority by a user-specified weight and subtracting the resulting product from the initial value;
adding a value to the resulting product that is proportional to the time between the predicted end of the job's execution and the job's deadline; and
subtracting a value from the resulting sum that is proportional to the tick value of the preferred path between the machine assigned to execute the job and any remote machine with which the job must exchange data.
