Single-Machine Scheduling with Multi-Criteria and Due- Windows

Area of Science:

• Operations Research
• Industrial Engineering
• Management Science

Background:

• Scheduling problems are often NP-hard, requiring efficient solution methods.
• Due-window constraints add complexity by defining job due dates as intervals.
• Multi-criteria optimization is crucial for balancing competing performance objectives.

Purpose of the Study:

• To develop a mathematical formulation for the multi-criteria single-machine scheduling problem with due windows.
• To propose dominance rules for identifying efficient job sequences.
• To reduce computational complexity while ensuring solution optimality.

Main Methods:

• Mathematical formulation of the scheduling problem.
• Analysis of special cases.
• Development and application of dominance rules (extending Minimum Slack Time and Earliest Due Date).
• Comparative analysis against the Complete Enumeration Method (CEM).

Main Results:

• The dominance-based approach yields reliable and efficient solutions comparable to CEM.
• Significantly reduced computational complexity compared to exhaustive methods.
• Demonstrated trade-offs between maximum earliness, maximum tardiness, and maximum late work.

Conclusions:

• The proposed dominance rules offer an effective method for multi-criteria scheduling with due windows.
• Practical implications for Just-in-Time (JIT) systems, improving cost efficiency and stability.
• Provides a foundation for extending to more complex scheduling environments (multi-machine, stochastic, dynamic).