Job shop scheduling: Classification, constraints and objective functions

Abstract

This paper by Abdolrazzagh-Nezhad and Abdullah provides a structured overview of Job Shop Scheduling Problems (JSSPs), focusing on their classification, the constraints they involve, and the objective functions used to evaluate schedules. The authors emphasize that JSSPs are NP-hard combinatorial optimization problems central to efficient manufacturing and production management, where optimal scheduling of jobs across machines with limited resources is critical for minimizing costs and improving performance.

The core of the article presents a comprehensive classification of JSSPs into fourteen distinct categories based on various facets such as job arrival processes, inventory policies, and the nature of processing times. This taxonomy includes well-known types like the deterministic (crisp) JSSP, flexible JSSP (where operations can be processed on multiple machines), and static versus dynamic JSSPs (distinguished by whether all jobs are available at the start or arrive continuously). It also covers more specialized variants such as the periodic, cyclic, pre-emptive, no-wait, just-in-time, large-scale, re-entrant, assembly, stochastic, and fuzzy JSSP. The fuzzy JSSP, which incorporates uncertainty in parameters like processing times and due dates using fuzzy set theory, is highlighted as a newer and important area reflecting real-world imprecision.

Beyond classification, the paper systematically details the constraints and objectives that define and drive solutions to these problems. The classic constraints are grouped into three types: precedence constraints (dictating the order of operations for each job), capacity constraints (governing machine usage and job independence), and release and due date constraints. The authors further elaborate on a range of "extra" constraints that add complexity to the basic model, such as multi-purpose machines, sequence-dependent setup times, maintenance activities, deteriorating jobs, and controllable processing times. These additional considerations make the problems more realistic but also significantly more challenging to solve.

Regarding objective functions, the review outlines the primary goals used to assess schedule quality. These include minimizing the makespan (total completion time), minimizing total weighted completion time (related to inventory costs), minimizing maximum lateness or total weighted tardiness (penalizing delays), and minimizing the weighted number of tardy jobs. The choice of objective depends on the specific production priorities, such as meeting due dates, reducing work-in-process inventory, or maximizing machine utilization.

The primary achievement of this paper is its synthetic and organizational contribution. It does not propose new algorithms but instead consolidates and clarifies the extensive landscape of JSSP research by offering a clear taxonomy and a structured compilation of constraints and objectives found in the literature. This work serves as a valuable reference for researchers and practitioners, helping them navigate the different problem variants and understand the specific challenges associated with each. By cataloging these elements in one place, the paper lays a foundational framework that aids in the selection of appropriate models and solution methodologies for specific industrial scheduling scenarios, ultimately supporting more informed and effective scheduling decisions.