Production Scheduling

Scheduling is a critical process used in production and the service sector common to allocate limited resources within a specific time scope to various tasks, with the primary goal of optimizing predetermined objectives. Resources can take different forms such as machines, labor, runways, information systems, or construction teams such as, while tasks may encompass diverse processes like production operations, flight planning, project phases, or computer operations.

In today’s competitive business environment, it has become inevitable for organizations to develop solutions focused on agility and efficiency. Meeting customer demands on time, with high quality and cost active effectiveness to meet carries significant importance for sustainable growth and competition advantage. Technological advancements and changing market conditions necessitate efficient resource utilization and effective management of production processes.

Production Scheduling

Production scheduling problems are commonly expressed using the α|β|γ notation, where α represents the production environment, β denotes processing characteristics and constraints, and γ indicates the objective to be optimized. Production environments are typically classified into single-machine and multi-machine settings. Multi-machine scheduling problems cover various production processes, including flow shop, flexible flow shop, job shop, and parallel machine systems.

Each production process has its own unique characteristics and constraints. Processing characteristics and constraints define various limitations within the production process, such as setup time, job preemption, no-wait constraints, and permutation constraints place. These constraints determine when and under what conditions each job is processed. The objectives to be optimized are typically performance measures such as makespan—the completion time of the last job—and total tardiness.

Scheduling problems can be classified as P problems (Polynomial) or NP problems (Nondeterministic Polynomial), depending on their size and complexity. P problems can be solved to optimality in polynomial time using mathematical algorithms, whereas the same cannot be guaranteed for NP problems. Therefore, various heuristic and metaheuristic methods have been developed. These methods do not guarantee optimal solution promise but allow for finding a near-optimal solution within a reasonable time opportunity.

Machine Environments

Single Machine

The single-machine problem provides a manageable model for addressing various scheduling topics and offers a context for examining different performance criteria and solution techniques. It is therefore one of the foundational pillars for comprehensively understanding scheduling concepts. To understand the behavior of a complex system, it is essential first to grasp its components, and the single-machine problem often arises as a component of larger scheduling problems. Sometimes, the single-machine problem can be solved independently, and the resulting solution can be integrated into the larger problem. For example, in multi-stage production processes, a bottleneck stage may exist, and analyzing this bottleneck using a single-machine model can determine key characteristics of the entire schedule.

Parallel Machines

In the Classical parallel machine scheduling problem, there are n jobs and m machines. Each job must be processed on one machine for a specified processing time. The goal is to construct a schedule that optimizes a specific performance criterion. Two key decisions are made during scheduling: sequencing (the order in which jobs are processed) and job-machine assignment (which job is assigned to which machine). While single-machine problems require only the determination of an optimal job sequence, multi-machine problems also require finding the optimal job-machine assignment.

Flow Shop

Flow shop arrangements refer to production environments where machines are arranged in a sequence and jobs follow a fixed route. Jobs begin on the first machine, pass through intermediate machines, and are completed on the final machine. Although this order is commonly referred to as a flow shop, real production systems often have more complex structures. Flow shop scheduling involves creating an optimal schedule for jobs that must pass through a specific sequence of machines. Jobs may have different processing times on each machine. This problem consists of two main components: m machines and n jobs, each requiring processing in the same order but with different processing times on each machine.

Flexible Flow Shop

In basic flow shop problems, each processing center consists of only one machine. However, if at least one processing center contains multiple machines, the problem becomes a flexible flow shop problem. Flexible flow shops are a generalized version of simple flow shops. Flexible flow shop scheduling problems combine characteristics of both flow shop and parallel machine scheduling. Process flexibility can be defined as the ability to perform different types of operations.

Operational flexibility, on the other hand, refers to the capacity to reorder the processing sequence for different piece types. Thanks to these two types of flexibility, any operation can be assigned to any parallel machine at a given stage. As these assignments change, processing times on machines may vary accordingly.

Job Shop

The classical job shop scheduling problem differs from the flow shop scheduling problem at one key point: the job flow is not unidirectional. The fundamental components of the problem consist of m machines and n jobs to be scheduled. Each job consists of a sequence of operations, similar to the flow shop model, but without a fixed order.

Although a job may contain any number of operations, the most common formulation of job shop scheduling problems assumes that each job has exactly m operations, each performed on a different machine. However, by adapting main concepts, more general cases can be applied where a job may visit the same machine multiple times or skip certain machines. Unlike the flow shop model, there is no designated starting machine for the first operation or a terminal machine for the last operation only.

Processing Characteristics and Constraints

Setup Time

Setup time is the preparation time required by a machine before it can begin processing a job. This preparation includes activities necessary for transitioning from the previous job to the next, such as adjusting machine settings, placing required equipment and materials, updating software, or installing specialized molds.

Preemption

Preemption allows a job being processed on a machine to be interrupted before completion and moved to another identical machine or resumed later on the same machine. This means a job can be temporarily halted to prioritize another job and then restarted later.

No-Wait Constraint

The no-wait constraint requires that jobs in a production system must not wait between operations. This means that once a job finishes processing on one machine, it must immediately begin processing on the next machine. Jobs must be scheduled so that no idle time occurs between consecutive operations.

Permutation

Permutation scheduling is a type of scheduling where the sequence of jobs is altered only by changing their relative order. In this type of scheduling problem, a specific sequence of jobs must be processed on a set of machines or workstations in a fixed order, and no other modifications beyond reordering the jobs are permitted.

Objective Function

Makespan

Makespan, the completion time of the last job, is the total time required to complete a set of jobs. Mathematically, makespan is the difference between the completion time of the last job and the start time of the first job. It represents the latest time at which all jobs are completed and is a key performance indicator for measuring production efficiency.

Total Tardiness

Total tardiness is a performance measure in production scheduling that quantifies how much each job is delayed beyond its due date. It represents the sum of the differences between the actual completion time and the due date for all jobs. Mathematically, the tardiness of a job is the difference between its completion time and its due date. If the completion time is earlier than or equal to the due date, the tardiness is zero (i.e., the job is completed on time). However, if the completion time exceeds the due date, the tardiness is positive and is added to the total tardiness difference.

Solution Approaches

Exact Methods

An exact algorithm is defined as an algorithm that always finds the optimal solution to an optimization problem, unlike heuristic approaches that may yield near-optimal solutions. A subset of these are convergence algorithms, which guarantee a proven bound on the ratio between the optimal solution and the solution produced by the algorithm. For NP-hard optimization problems, polynomial-time convergence algorithms are often available, while the best-known exact algorithms require exponential time.

The branch-and-bound algorithm can be considered a direct approach for solving scheduling problems. It is a design paradigm for discrete and combinatorial optimization problems. In the branch-and-bound algorithm, the set of candidate solutions is represented as the root of a tree, and subsets of the solution space are represented by the tree’s branches. The algorithm explores branches and establishes upper and lower bounds for the optimal solution. It iteratively eliminates solutions until the optimal solution is found.

Heuristic Methods

Heuristic methods are procedures for searching for a satisfactory solution to a given target, without guaranteeing optimality. Heuristic methods can be applied to problem solving, learning systems, and optimization. The group of heuristic methods is divided into constructive procedures and improvement procedures. Constructive procedures create solutions by building them job-by-job or machine-by-machine stage. Improvement procedures refer to methods that refine an initial or constructed solution. Examples of heuristic methods include the NEH, CDS, and Palmer algorithms.

Metaheuristic Methods

Metaheuristic methods are iterative processes that improve potential solutions. In other words, metaheuristic approaches are a collection of mathematical ideas that can be used to define heuristic algorithms suitable for a broad range of problems. Tabu Search, Genetics Algorithms, Simulated Annealing, Particle Swarm Optimization, and Ant Colony Optimization are examples of metaheuristic methods.