Title: Task And Resource Integration Method and System Inventor(s): D. Zachary James, Douglas J. James, Gary J. Bishop.
Assignee: None BACKGROUND OF THE INVENTION
Field of the Invention This invention relates generally to task automation. In particular, a system and method for task integration, according to the invention, considers both task components and available resources.
Description of Related Art There are a number of products and patents in the art that deal with producing schedules or controlling machine operation based on jobs or tasks that need to be completed. A task exists when some operation is required to be performed on a object. A job is composed of one or more tasks that are related in some way.
Various levels of sophistication have been employed to optimize how quickly or on schedule a job is completed. However, there has been little improvement in the way resources are handled especially where multiple resources with different attributes exist.
Improving the integration and processing of operations on tasks which compose a job is generally not considered. Examples of areas that require both task and resource scheduling would be any operation that has several resources with varying attributes and several tasks with varying requirements, where coordinating the tasks with the resources would -___.~
be a benefit. Real-world examples include medical imaging equipment, where a hospital may have several imaging machines (resources) of varying resolution, penetration and speed, and multiple imaging tasks for patients (objects with associated tasks) that require imaging at different resolutions, speeds and penetration depths.
Canadian Patent Application CA2302332 envisions a process of tracking work progress and the assignment of tasks to a workforce. The workforce can be scaled in size, but are considered to be composed of uniform elements (the employees in the workforce) all equally capable of performing any task within their geographic area.
United States Patent 5559710 documents a system and method for scheduling orders into a factory with many machines. The machines themselves are treated as uniform units that are completely interchangeable while the nature of the job is used to determine an optimized schedule.
United States Patent 5890131 provides a project optimization tool that can define and display a processing path for a job from beginning to completion though a number of individual tasks.
United States Patent 6256651 illustrates workflow management software where tasks can be assigned to and split amongst several users (resources).
All resources are considered interchangeable and the primary user or manager can graphically adjust how much time each user spends on each task.
United States Patent 5408663 provides methods for optimizing a project schedule for a job by selecting a task from a series of tasks then iteratively making small modifications to said task such that an optimized project schedule is produced.
Further the schedule allows the assigned resource to be tested to see if the task duration can be shortened and if the mix of resources used for one task is optimum.
As can be seen from the above known schemes significant effort has be placed on recognizing and attempting to optimize the order that a series of tasks in a job is processed in. Little effort has been expended in actually analyzing the resources available or trying to optimally assign those resources to individual tasks, and in most cases, resources to complete a task are simply treated as interchangeable homogeneous elements that have no inherent advantages over each other.
Further, these known systems are typically focused on jobs where tasks are ordered in a fixed way. In a factory situation there are often a number of tasks that may be completed in many different orders and therefore these tasks cannot be optimally handled by a system that enforces a particular order for the tasks. In addition, the concept of a job containing multiple tasks is generally not applicable to a factory situation where a large number of jobs would be composed of only one task and therefore cannot be optimized simply by ordering (such as a metal punching operation for example).
Therefore, there exists a need for a task scheduling system that can combine all available knowledge about both the task requirements and the resource attributes to provide a meaningful and optimal schedule for handling said tasks.
SUMMARY
The present invention provides a method and system for task scheduling that assesses the components of the task and the available resources to carry out the task.
In one aspect of the invention, several resources and their attributes and several tasks and their requirements to be scheduled are input into a system database.
The tasks are then coordinated with given resources such that total completion time, cost, or other goals are satisfied by the schedule. This task and resource coordination preferably analyses a plurality of data input by a user, such as several steps and requirements, associated resources, and the like. The invention may also include, but is not limited to, cost, time, or other factors for analysis. Unlike current solutions, the present invention is preferably dynamic such that any task, resource or requirements change will preferably be reflected immediately in a resultant output schedule or by controlling the resource directly.
Further features of the invention will be described orwill become apparent in the course of the following detailed description.
BRIEF DESCRIPTION OF THE DRAWINGS
In order that the invention may be more clearly understood, the one or more embodiments thereof wilt now be described in detail by way of example, with reference to the accompanying drawings, in which:
Fig. 1 is a block diagram of a scheduling system according to an aspect of the invention;
Fig. 2 is a diagram depicting the operation of the bid generator 106 of Fig.
1;
and Fig. 3 is a diagram depicting the operation of the scheduler 108 of Fig. 1.
DETAILED DESCRIPTION OF THE INVENTION
Fig. 1 is a block diagram of a scheduling system according to an aspect of the invention. Fig. 1 shows an input graphical user interface (GUI) 102 where a user can input resource attributes or task requirements. The input information is fed into a system database 104 for storage, and into a resource/task bid generator 106, which is described in further detail below with reference to Fig. 2. Each task can be entered as a complete description, or if a similar task has been completed previously the task can be entered as a single part-number to speed up entering task information. Resource entry can be done simply using the name of the resource for those resources already defined.
Resources are input to the system when they are first used. The user can also enter resources that are not currently available to see what impact said resources would have on the system schedule. In this way a user can use the dynamic features of the system to determine what resources and what aspects of those resources would be most beneficial to the current task scheduling situation. This information can be used to make more educated decisions about future resources to be purchased. The bid generator outputs "bid"
information for each resource as if the respective resources were to complete each task.
Parameters of interest such as cost, set-up and processing duration make up part of a bid, although other types of information may also be included in a bid. Bid information is preferably configurable by a scheduling system user or owner in accordance with the parameters of interest that should be considered when coordinating tasks and resources.
~ _ The scheduler 108 collects the bids and determines the best possible order and resource assignments for the tasks and outputs a schedule or can control resources directly 110. If the schedule output is directed directly at the user, the schedule could be displayed graphically on a computer screen or on remote terminals.
Alternatively a schedule could be printed in text form much like a report or to-do list and this could be provided to the machine operators. Updated schedules could also be sent wirelessly to hand-held computers, phones or pagers carried by the machine operators to ensure schedule changes were communicated as quickly as possible. If sufficient automation is present the scheduler could control the resources directly either through direct wired control, or through some kind of hardware/software interface that parses the schedule to determine proper control signals to apply to the machine resource.
The input graphical user interface 102 and output schedule 110 can use a number of different templates 105 for display, processing and outputting of information without significantly modifying the structure of the database 104, bid generator 106 or scheduler 108 components of the design.
Further, input GUI 102 and output/control modules 110 may each exist as a plurality of devices either within a single facility or in multiple facilities connected by a data network. The same or a different network may be used to transport status information to the system data from sensors or controllers on remote or local resources indicating for example the unavailability of particular resources which may require re-scheduling by the system.
As an example of the use of the described system, it may be applied to a laser cutting shop consisting of a number of disparate resources or machines each capable r of meeting the requirements of a sub-set of a series of tasks with a process duration and process cost which is different. By applying a series of conditional tests which compare resource attributes with task requirements the software system determines which machines are capable of performing the task and further, using embedded models of the task/resource interaction, calculates the process duration and process cost for each such machine. The output for each resource capable of performing the task is considered a bid by that machine and, in a preferred embodiment a bid may consist of, but not be limited to, a process duration and a process post. All the bids, together with the time constraints of each task, and the objective function for scheduling, are presented to the Scheduler. The resulting schedule can indicate the optimum arrangement of tasks in time and by machine to ensure that the scheduling goal is reached. The schedule may also indicate maintenance breaks, shift structure, and requirements for machine modification such as focussing lens changes.
In a preferred embodiment, the input GUI 102, bid generator 106, scheduler 108 and output/control module 110 are implemented in computer software. These modules may be installed on a computer which also includes a data store for the system database 104, although the database and software modules need not necessarily be resident on the same computer. For example, a scheduling system terminal may run the input GUI
102, the database 104 may be stored at a file server, and the bid generator 106, scheduler 108 and the output/control module 110 may be executing on a scheduling server, all within the same local area network (LAN) or other network system through which the various components can exchange information.
All modules may be written in a number of computer languages including, but not limited to, machine language, C, C++, or Java. Higher level languages may also be used and components may be used and arranged in a manner to provide the required functionality. Examples of software techniques that could be used to implement any or all of the modules may include expert systems, neural networks, genetic algorithms and constraint programming. Fig. 2 is a diagram depicting the operation of the bid generator 106 of Fig. 1. Fig. 2 illustrates in more detail how the bid generator 106 accepts resource or machine information 202 and task information 203, then computes bids for each task on each resource and outputs the information as a series of bids 201.
In accordance with an aspect of the present invention, resource attributes need not exactly match task requirements in order for the bid generator 106 to generate a bid for a particular resource to complete a specific task. The resource simply needs to be able to complete the task in some way, even if that requires time or costs in excess of other resources. The scheduler 108 may determine that additional cost, time or other parameters are an acceptable compromise in order to fit or otherwise improve other areas of the schedule.
Each resource can have attributes that vary. An attribute can be, but is in no way limited to, the cost of electricity used to run a given machine. The bid generator can access the most current value of such varying attributes through the Internet, by user input, or through another information service. Values of the attributes could also be provided with forward looking information such as the expected price of electricity at a certain time in the future, for example the price of electricity may be known to be lower during the night shift.
Therefore bids will be adjusted such that high energy demanding jobs are given preference _g_ at night.
Some tasks require certain options to be enabled on a given resource. In many cases these options may require additional time or cost to be added to the schedule which in turn will impact the bid. An example would be a laser cutter that has a choice of two lenses depending on the task requirements. The previous task may have had the required lens installed, or a new lens may be required for the new task.
Therefore the bids can be affected by previous tasks completed on the resources. These resource set-up change requirements are noted with the bid information for evaluation by the scheduler system.
Fig. 3 is a diagram depicting the operation of the scheduler 108 of Fig. 1.
Fig.
3 illustrates in more detail how the scheduler 108 processes bids 201 from the bid generator 106 and various optimisation criteria 302, such as cost or completion time, will output a schedule or machine control signal 110. If the scheduler 108 cannot find a schedule that meets all criteria, it will highlight the offending tasks) and can either schedule a best-fit or can alert the user that a compromise is required.
The optimisation criteria may be determined by the user or automatically determined by the scheduler according to the current conditions or demands.
For example, when there are only a few tasks to complete, cost may be automatically given higher relative importance than completion time.
An example of a potential application for the invention is in a laser metal cutting factory. Each laser may have different attributes including for example maximum power, cut resolution and cut speed. Those skilled in the art will appreciate that there are many other possible attributes of these resources, but for simplicity we will focus on these _g_ three. Customers would have specific task requirements for their metal pieces that could include a due-date, resolution, and material thickness. It will not always be obvious which resource should work on which task, as a low resolution item might be adequately handled by several different resources but with different speeds, while a high resolution task might only be handled by one resource and would therefore need priority on that specific resource. In addition, different resources may handle several thicknesses of material but at different speeds or with certain resolution changes, further complicating the resource selection. It may also be advantageous to handle tasks in different orders than originally presented. A significant advantage of the present invention is that resources and tasks may be scheduled and coordinated in accordance with such criteria, even conflicting criteria.
The above description relates to the preferred embodiment as an example of the invention. Many variations on the invention will be obvious to those skilled in the art, and such obvious alternatives are within the scope of the invention as described and claimed, whether or not expressly described.