431 Scheduling

What is scheduling? What is its operational purpose?

• Setting operational timing for equipment, facilities, and human activities to complete required tasks over time.

• Allocating limited resources to answer the operational "when" question.

What parameters and job attributes define a Classical Job Shop Scheduling problem?

• Processing n jobs across m machines.

• Each job consists of a strict, fixed sequence of operations.

• Each operation is assigned to a specific, dedicated machine.

What three physical constraints govern operation processing in Classical Job Shop Scheduling?

• Precedence Constraint: An operation cannot start until all preceding operations in its job sequence complete.

• Non-Preemption Constraint: Processing of an operation cannot be stopped or interrupted once started.

• Single-Capacity Constraint: Each machine can process at most one operation at a time.

How are Flowtime and Tardiness calculated, and what does each evaluate?

• Flowtime (Finish Time - Arrival Time): Measures total time spent in the facility and internal processing efficiency (work-in-process inventory).

• Tardiness (max{Finish Time - Due Date, 0}): Measures non-negative delay past a job's deadline and customer delivery performance.

What operational traits separate Static JSS, Dynamic JSS, Flexible JSS, and Dynamic Flexible JSS?

• Static JSS: All job arrivals and attributes are fully known upfront.

• Dynamic JSS: Jobs arrive unpredictably over time, or dynamic events like machine breakdowns occur.

• Flexible JSS: Operations can run on a set of candidate machines with machine-dependent processing times.

• Dynamic Flexible JSS (DFJSS): Combines candidate machine choices with unpredictable job arrivals over time.

What two distinct decisions must a scheduler make in Dynamic Flexible Job Shop Scheduling?

• Routing (Machine Assignment): Deciding which candidate machine will process an operation.

• Sequencing (Operation Sequencing): Deciding which queued operation an idle machine will process next.

How do Machine-Oriented and Job-Oriented Gantt charts visually format a schedule?

What two overlap rules determine whether a schedule is feasible?

• Machine-Oriented Gantt Chart: Y-axis lists machines and X-axis lists time, displaying machine utilization, idle periods, and queues.

• Job-Oriented Gantt Chart: Y-axis lists individual jobs and X-axis lists time, displaying timeline progress and completion for each job.

• No Machine Overlap: No time overlap of multiple operations on the same machine.

• No Job Overlap: No time overlap of multiple operations belonging to the same job.

How do processing time calculations differ across Identical, Uniform, and Unrelated parallel machine environments?

• Identical: Processing time depends solely on the job (p_j).

• Uniform: Processing time scales inversely by machine speed (p_j / s_i).

• Unrelated: Processing time depends on the specific job-machine pairing (p_ij).

How do operation sequence rules and machine assignments formally distinguish Open-Shop (O), Flow-Shop (F), and Job-Shop (J) problems?

• Open-Shop (O): Operations can be processed in any arbitrary order across machines.

• Flow-Shop (F): Operations are processed in a fixed order where operation i always runs on machine i.

• Job-Shop (J): Operations are processed in a fixed order where each operation O_ij is tied to a specific dedicated machine U_ij.

What system attribute is specified by each parameter in alpha | beta | gamma notation?

• alpha: Defines the machine environment layout.

• beta: Defines job characteristics and operational constraints.

• gamma: Defines the target optimization objective to minimize.

What are the three scheduling approaches and how do they compare in terms of benefits vs trade-offs?

• Exact Methods: Guarantee optimal schedules, but exponential time complexity restricts them to small static problems.

• Heuristic Search (GAs): Effective for large static problems, but inefficient dynamically because any event requires a full reschedule.

• Dispatching Rules: Scalable and instantly reactive to real-time events via local priority scores, though can be reliant on manual, trial-and-error design.

What is the fundamental difference between heuristic and hyper-heuristic search?

• Traditional Heuristics: Search directly in the solution space (evaluating specific schedule configurations).

• Hyper-Heuristics: Search in the heuristic space (evaluating or constructing algorithms/rules that generate schedules).

How do Heuristic Selection and Heuristic Generation differ in what they construct?

• Heuristic Selection: Dynamically picks which existing low-level rule (e.g., SPT, FCFS) to apply at each problem state $\rightarrow$ produces a sequence of heuristics.

• Heuristic Generation: Combines primitive building blocks (features and operators) to construct a brand-new priority rule $\rightarrow$ produces a comprehensive heuristic (e.g., GP syntax tree).

What are the two trees in a GP scheduling heuristic, what state inputs does each use, and how is a real-time choice made?

• Routing Rule Tree: Assigns operations to candidate machines using machine-level state (queue lengths, wait times).

• Sequencing Rule Tree: Orders queued operations for an idle machine using job/operation-level state (processing times, work remaining, weights).

• Real-Time Execution: Plugs live state values into the tree formula and picks the candidate option with the lowest priority score.

How do standard GP crossover and mutation operate on syntax trees?

Why does standard GP crossover hinder evolutionary convergence?

• GP Crossover: Selects a random node in two parent trees and swaps their respective subtrees.

  • Destructive Crossover: Random subtree swapping frequently disrupts beneficial functional subtrees (building blocks) in high-performing parents and introduces ineffective or contradictory subtrees. This degrades offspring fitness and forces evolution to re-learn lost logic.

• GP Mutation: Selects a random node in a parent tree, deletes its subtree, and inserts a newly generated random subtree.

How does guided crossover / recombinative guidance work?

Evaluates subtree quality to surgically remove identified unimportant subtrees from a parent tree and replace them specifically with important subtrees from another parent tree, eliminating destructive random swaps.

How does Feature Frequency evaluate subtree importance?

• Mechanism: Counts terminal feature occurrences across top-performing population individuals.

• Logic: Subtrees containing a higher concentration of features favored by selection across the population are rated as important.

How does Decision Vector Correlation evaluate subtree importance?

• Mechanism: Computes the Pearson correlation coefficient between an isolated subtree's decision ranking vector and the full parent tree's decision ranking vector across scheduling scenarios.

• Classification: High positive correlation (+1) = Important (drives parent logic); Low/Negative correlation ($\le 0$) = Unimportant (neutral or contradictory choices).

What primary computational bottleneck in GP hyper-heuristics do surrogate models address?

• Computational Bottleneck: Evaluating GP rule fitness requires executing discrete-event simulation runs across thousands of dynamic job arrivals, making evaluation extremely slow.

• Surrogate Function: Replaces full simulation runs with a fast computational proxy to rapidly approximate rule fitness.

What core trade-off governs the use of surrogate models in evolutionary computation?

• Speed Advantage: Drastically reduces evaluation time per individual during evolutionary search.

• Accuracy Cost: Introduces approximation error relative to full simulation, but provides sufficient ranking accuracy to steer selection.

Why is distance in genotype space an ineffective measure of program similarity in GP, and how does phenotype space address this?

• Genotype Limitation: Structural syntax tree comparisons fail because structurally distinct trees can execute identical scheduling choices.

• Phenotype Measure: Quantifies functional behavior via a Phenotypic Characterization ($PC$) vector, recording decision rankings across reference scenarios.

How does a KNN-based surrogate estimate the fitness of a newly generated GP rule?

• Distance Calculation: Computes Euclidean distance between individuals in phenotype space using their $PC$ vectors.

• Fitness Estimation: Approximates fitness using the known fitness values of the individual's $K$ nearest phenotypic neighbors.

How do simplified simulation models operate as surrogates, and what key condition determines their validity?

• Mechanism: Evaluates GP rules on scaled-down setups (e.g., fewer machines or shorter simulation horizons).

• Validity Condition: Relies on maintaining a high rank-correlation between the simplified model and the full simulation environment.

What challenge arises when rotating training instances across generations in KNN surrogates, and how is it resolved?

• Challenge: Rotating training instances shifts the baseline fitness scale each generation, making raw historical fitness values non-comparable.

• Resolution: Fits a linear regression model using elite individuals to map historical fitness scores onto the current generation's scale before KNN estimation.

What is simulation fidelity in surrogate modeling, and how does a multi-fidelity surrogate framework operate?

• Fidelity Definition: The scale and exactness of the simulation setup (High Fidelity = full shop simulation; Low Fidelity = simplified model).

• Framework Operation: Divides the population into sub-populations at different fidelity levels and uses knowledge transfer to migrate top rules from fast, low-fidelity pools into high-fidelity pools for refinement.

How does phenotype-based grouping reduce the number of full fitness evaluations?

• Grouping: Clusters offspring into groups based on identical or near-identical $PC$ vectors.

• Sampling Strategy: Fully evaluates only one representative individual per group (the smallest tree) and assigns its fitness score to the rest of the group.

What primary computational and structural drawbacks occur when providing GP with an exhaustive terminal feature set?

• Structural Cost: Generates overly complex, bloated trees that lack human interpretability.

• Computational Cost: Expands the search space, increasing training time and risking search stagnation due to the curse of dimensionality.

How does feature dataset availability in GP hyper-heuristics differ from standard supervised machine learning?

• Standard Machine Learning: Uses a fixed, pre-existing dataset.

• GP Hyper-Heuristics: Has no starting dataset; it builds its own data during the run by logging which features each generated tree used and how well that tree scored.

  • A set of GP trees: [features in the GP tree, fitness]

What underlying assumption governs feature frequency-based selection in GP populations?

Terminal state features that occur frequently across top-performing population individuals are the primary drivers of rule quality.

How does contribution-based feature selection evaluate whether a terminal feature actively enhances a GP rule?

• Masking Procedure: Replaces the target feature with a constant ($f=1$) inside the syntax tree.

• Contribution Metric: Subtracts original rule fitness from masked rule fitness ($C_f^r = \text{fitness}(r \mid f=1) - \text{fitness}(r)$); a positive value confirms active functional benefit.

What is the complete, two-stage process of contribution-based feature selection?

• Phase 1 (Filter Features): Runs a GP search with diversity controls (niching) to collect candidate rules, tests feature contributions by masking, and keeps features that improve performance in over 50% of evaluated base rules.

• Phase 2 (Adapt & Re-build Rules): Restricts a new GP search to the reduced feature set. It identifies top Phase 1 rules (via knee-point detection) and builds new trees that mimic their decision behavior using only the selected features.

What fundamental limitation of standard Genetic Programming in dynamic scheduling does Multitask Learning address?

• Standard GP Limitation: Trains a rule for one isolated scenario at a time from scratch. If shop conditions change, evolution must restart completely.

• Multitask Solution: Solves multiple scheduling tasks simultaneously in a single run by sharing useful code subtrees across tasks.

What is the step-by-step execution flow of a Multitask Evolutionary Algorithm across multiple tasks?

• Init & Full Evaluation: Test an initial population across all tasks to find where each rule excels.

• Task & Fitness Assignment: Calculate Factorial Ranks, assign each rule a Skill Factor (its specialty task), and calculate its Scalar Fitness.

• Mating & Focused Evaluation: Breed rules using Assortative Mating and test new offspring only on their assigned specialty task.

• Survival Selection: Merge parents and offspring, select top rules based on Scalar Fitness, and repeat until convergence.

What are Factorial Rank, Skill Factor, and Scalar Fitness in Multitask GP, and how do they work together?

• Factorial Rank: An individual's performance rank on a specific task relative to the population.

• Skill Factor: The specific task where an individual achieves its best (lowest numerical) Factorial Rank, defining its specialty.

• Scalar Fitness: A score calculated as $\frac{1}{\text{Best Factorial Rank}}$ that flips placement ranks into a standardized 0-to-1 fitness score, allowing individuals specializing in different tasks to compete fairly in a single population.

Why does Assortative Mating use different breeding rules for same-specialty vs. different-specialty parents?

• Same Specialty Parents: Perform standard crossover because combining ideas for the same task improves that task's logic.

• Different Specialty + High Roll ($rand \ge rmp$): Mutate independently because blindly swapping subtrees between different problems ruins both rules' logic.

• Different Specialty + Low Roll ($rand < rmp$): Perform cross-task crossover because swapping subtrees occasionally transfers useful general building blocks between problems.

What is Vertical Cultural Transmission in Multitask GP?

• Definition: An evolutionary inheritance mechanism where an offspring created through cross-task crossover randomly inherits the specialty task label (Skill Factor) of one of its parents.

How does Origin-Based Offspring Reservation protect solution quality during cross-task crossover?

• Mechanism: When crossing parents from different task pools, it retains only the child whose main tree foundation originated from the home task's parent, discarding the child rooted in the foreign parent.

• Benefit: Allows a rule to borrow a helpful foreign subtree without losing its foundational identity for its home task.

What is Surrogate-Assisted Multitask GP, and why is it used?

• Core Concept: Combines multitask evolutionary search with fast surrogate models to eliminate the computational bottleneck of evaluating transferred rules through full, slow factory simulations.

• Mechanism: Fast surrogate models rapidly screen candidate subtrees in milliseconds, sending only the most promising candidates to full simulation.

How does task relatedness prevent negative transfer in Multitask GP?

• Mechanism: Measures decision-choice divergence (KL Divergence) between tasks; lower divergence yields a higher relatedness score ($R = \frac{1}{1 + D_{KL}}$).

• Selection Rule: Tasks with higher relatedness scores are prioritized for code sharing, blocking code transfer between incompatible tasks.

What is the trade-off between plasticity and stability in sequential lifelong learning?

• Plasticity: The capacity of a system to adapt and acquire new knowledge when a brand-new task arrives.

• Stability: The capacity of a system to preserve its performance on previously learned tasks.

What is Catastrophic Forgetting, and why does standard fine-tuning cause it in sequential learning?

• Definition: The severe loss of performance on past tasks when an algorithm adapts to a new task.

• Cause: Standard fine-tuning updates tree structures to optimize the new task, overwriting the functional subtrees required for previous tasks.