Research Reports from the Department of Operations
Document Type
Report
Publication Date
4-1-1978
Abstract
This paper explores the current theoretical understanding of static job shop scheduling, focusing on assigning tasks to processors while optimizing objectives such as timing and sequence. Tasks, characterized by parameters like processing time and due dates, may form dependent groups (jobs) or remain independent. The study distinguishes job shop scheduling from broader scheduling fields such as production and manpower scheduling. Combinatorial challenges in this domain have been extensively studied, with optimal scheduling rules available for simpler cases, while complex problems often rely on computationally intensive algorithms. The paper outlines efficient algorithms with polynomial time complexity and highlights insights from complexity theory, which identifies problems unlikely to be solvable efficiently. Subsequent sections provide definitions, notations, and algorithmic analysis.
Keywords
Operations research, Production scheduling, Scheduling--Mathematical models, Combinatorial optimization
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 437
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Emmons, Hamilton, "A Survey of Static Job Shop Scheduling Theory" (1978). Research Reports from the Department of Operations. 580.
https://commons.case.edu/wsom-ops-reports/580