Understanding Key Dates in Scheduling

Recap: Time Constraints in α|β|γ Notation

Recall from our previous lesson:

• The β field describes job characteristics. The term r_j signifies that jobs have release dates.
• The γ field defines the objective function. Objectives like L_max (maximum lateness) or ∑T_j (total tardiness) are directly related to due dates.

Let's now formally define these terms and explore their impact on scheduling problems.

1. Release Dates: When Can a Job Start?

A release date, denoted as $r_j$, is the earliest time at which job $j$ becomes available for processing. Before its release date, a job simply cannot be scheduled, even if a machine is free.

In many real-world scenarios, jobs are not all available at the beginning of the planning horizon. For example, in a factory setting, raw materials for a specific job might not arrive until a certain time. In a computing environment, a task might depend on the output of a process that finishes at a specific time.

The Role of Release Dates

The primary role of release dates is to constrain the set of schedulable jobs at any point in time.

• Default Assumption: If r_j is not mentioned in a problem's β field, it's assumed that all jobs are available at time 0 ($r_j=0$ for all $j$).
• Introducing Idle Time: When non-trivial release dates exist, it may be optimal for a machine to remain idle, waiting for a high-priority job to be released, rather than immediately starting a currently available but lower-priority job.
• Increasing Complexity: The introduction of release dates can dramatically increase the computational complexity of a scheduling problem. Many problems that are easy to solve when all jobs are available at time 0 become NP-hard when release dates are added. We will see a concrete example of this shortly.

2. Due Dates and Deadlines: When Should a Job Finish?

While release dates constrain the start of a job, due dates and deadlines relate to its completion. It's crucial to distinguish between these two terms.

• A due date ($d_j$) is a target completion time for job $j$. Finishing after the due date is undesirable and usually incurs a penalty, but it is not forbidden.
• A deadline (${\bar{d}}_j$) is a hard constraint. Job $j$ must be completed by time ${\bar{d}}_j$. Any schedule that violates a deadline is considered infeasible. In the α|β|γ notation, deadlines are often modeled as a special type of constraint in the β field, while due dates are typically used to define the objective function in the γ field.

In your industrial engineering context, due dates represent commitments to customers, while deadlines might represent physical constraints, such as a chemical that will spoil if not processed by a certain time.

The Role of Due Dates: Defining Performance

The primary role of due dates is to provide a reference point for measuring the timeliness of a schedule. From due dates, we derive several key performance metrics.

Let $C_j$ be the completion time of job $j$. The most important metrics related to its due date $d_j$ are:

• Lateness ($L_j$): Defined as $L_j=C_j-d_j$.
  • If $L_j>0$, the job is tardy or late.
  • If $L_j<0$, the job is early.
  • If $L_j=0$, the job is on time.
• Tardiness ($T_j$): Defined as $T_j=\max (0,L_j)$.
  • Tardiness is always non-negative. It measures how late a tardy job is and ignores any earliness. This is often more practical, as there's usually a cost for being late but no reward for being early.
• Earliness ($E_j$): Defined as $E_j=\max (0,-L_j)=\max (0,d_j-C_j)$.
  • This measures how early a job is completed. In just-in-time (JIT) systems, both earliness (which increases inventory costs) and tardiness are penalized.

These job-level metrics are then aggregated into objective functions for the γ field, such as:

• L_max: Minimize the maximum lateness (${\max }_j{L}_j$). This focuses on the worst-case performance, aiming to ensure no single job is excessively late.
• ∑T_j: Minimize the sum of tardiness. This aims to reduce the total amount of lateness across all jobs.
• ∑U_j: Minimize the number of tardy jobs, where $U_j$ is 1 if job $j$ is tardy ($T_j>0$) and 0 otherwise.

A Concrete Example

Let's look at how these values are calculated. The table below shows a schedule for six jobs, ordered by the Shortest Processing Time (SPT) rule. "Flow time" is another term for completion time ($C_j$).

Let's trace the calculation for Job B:

1. Sequence: Jobs are processed in the order A, C, E, B, D, F.
2. Completion Time ($C_B$): Job A takes 2 hours, C takes 3, and E takes 4. Job B starts after E finishes at time 9 and takes 6 hours. So, $C_B=9+6=15$.
3. Due Date ($d_B$): The table states the due date for Job B is 8.
4. Lateness ($L_B$): $L_B=C_B-d_B=15-8=7$. Job B is 7 hours late.
5. Tardiness ($T_B$): $T_B=\max (0,L_B)=\max (0,7)=7$.

As you can see, the due date acts as the benchmark against which the schedule's performance is measured.

Conclusion

In this lesson, we have formally defined and examined the roles of three fundamental time-based concepts in scheduling:

• Release Dates ($r_j$): Act as availability constraints, dictating the earliest start time for a job. They are part of the problem definition (β field) and can significantly increase scheduling complexity.
• Due Dates ($d_j$): Serve as performance targets. They are used to calculate lateness and tardiness, which form the basis for many common objective functions (γ field).
• Deadlines (${\bar{d}}_j$): Are hard constraints that define the latest possible completion time for a job. Violating a deadline results in an infeasible schedule.

You now understand how these elements move us from simple sequencing to more realistic and challenging time-constrained optimization problems, which are at the heart of scheduling research and practice.

In the next lesson, we will continue our exploration of core concepts by comparing and contrasting the most common scheduling objectives we introduced today, such as makespan (C_max), total completion time (∑C_j), and various due-date-related metrics. This will help you understand the trade-offs involved in choosing an objective for a given industrial problem.