Job Scheduling

Job Scheduling (JS) has a long history in the operations research field (recall that constraint programming, on the other hand, originated in AI). Typically, JS problems involve assigning a set of activities to a limited number of resources with consideration given to time and ordering limitations.

The core entity of a JS problem is the activity. Activities are used to model precisely what their name suggests, activities - be it anything from painting (in the context of building a house) to adding the chocolate chips (in the context of baking cookies). Activities are typically represented by 3 ranges of numeric values: the earliest start time, the latest end time, and the duration of the activity. Activities can depend on one another (in our house example, the framing and drywall would have to be complete before painting), and activities require resources (some paint, a paintbrush, a painter, etc.).

The other essential entity of a JS problem (as you may have surmised) is the resource. Activities interact with resource(s) for processing, and resources are classified differently depending on their potential interaction with activities:

• Unary - resource that can process only one activity at a time
• Discrete - the number of activities supported by a discrete resource is determined by its available capacity over time
• Reservoir - resource that can be both consumed and/or produced by an activity (ie. its capacity can go down as well as up)

As is commonly the case, variations and extensions of these standard resources exist.

Solving a JS problem consists of associating (assigning) activities to resources and determining the start, end, and duration of each activity. As with standard constraint satisfaction problems, a goal or objective is commonly used. In the realm of Job Scheduling, common goals include minimizing makespan (the difference between the start of the first activity and the end of the last) or minimizing resource cost.

A significant amount of research has been done into creating intelligent methods of solving JS problems. One such method is to treat a Job Scheduling problem as an extension of a constraint satisfaction problem. Commonly referred to as 'Constraint-Based Scheduling', this approach is well-suited for solving real-world scheduling problems, and it is the technique used in the jOpt project.

Development Status

An alpha-version of the job scheduling component of the jOpt project has been released and is available for download.