Chapter 9 Sequencing and scheduling: Algorithms and complexity

Efficient algorithms for scheduling equal-length jobs with processing set restrictions on uniform parallel batch machines

We consider the problem of scheduling jobs with equal lengths on uniform parallel batch machines with non-identical capacities where each job can only be processed on a specified subset of machines called its processing set. For the case of equal release times, we give efficient exact algorithms for various objective functions. For the case of unequal release times, we give efficient exact algorithms for minimizing makespan.

Innovative System for Scheduling Production Using a Combination of Parametric Simulation Models

The article deals with the design of an innovative system for scheduling piece and small series discrete production using a combination of parametric simulation models and selected optimization methods. An innovative system for solving production scheduling problems is created based on data from a real production system at the workshop level. The methodology of the innovative system using simulation and optimization methods deals with the sequential scheduling problem due to its versatility, which includes several production systems and due to the fact that in practice, several modifications to production scheduling problems are encountered. Proposals of individual modules of the innovative system with the proposed communication channels have been presented, which connect the individual elements of the created library of objects for solving problems of sequential production scheduling. With the help of created communication channels, it is possible to apply individual parameters of a real production system directly to the assembled simulation model. In this system, an initial set of optimization methods is deployed, which can be applied to solve the sequential problem of production scheduling. The benefit of the solution is an innovative system that defines the content of the necessary data for working with the innovative system and the design of output reports that the proposed system provides for production planning for the production shopfloor level. The DPSS system works with several optimization methods (CR—Critical Ratio, S/RO—Slack/Remaining Operations, FDD—Flow Due Date, MWKR—Most Work Remaining, WSL—Waiting Slack, OPFSLK/PK—Operational Flow Slack per Processing Time) and the simulation experiments prove that the most suitable solution for the FT10 problem is the critical ratio method in which the replaceability of the equipment was not considered. The total length of finding all solutions by the DPSS system was 1.68 min. The main benefit of the DPSS system is the combination of two effectively used techniques not only in practice, but also in research; the mentioned techniques are production scheduling and discrete computer simulation. By combining techniques, it is possible to generate a dynamically and interactively changing simulated production program. Subsequently, it is possible to decide in the emerging conditions of certainty, uncertainty, but also risk. To determine the conditions, models of production systems are used, which represent physical production systems with their complex internal processes. Another benefit of combining techniques is the ability to evaluate a production system with a number of emerging problem modifications.

A Self-Adaptive Differential Evolution Algorithm for Scheduling a Single Batch-Processing Machine With Arbitrary Job Sizes and Release Times

Batch-processing machines (BPMs) can process a number of jobs at a time, which can be found in many industrial systems. This article considers a single BPM scheduling problem with unequal release times and job sizes. The goal is to assign jobs into batches without breaking the machine capacity constraint and then sort the batches to minimize the makespan. A self-adaptive differential evolution algorithm is developed for addressing the problem. In our proposed algorithm, mutation operators are adaptively chosen based on their historical performances. Also, control parameter values are adaptively determined based on their historical performances. Our proposed algorithm is compared to CPLEX, existing metaheuristics for this problem and conventional differential evolution algorithms through comprehensive experiments. The experimental results demonstrate that our proposed self-adaptive algorithm is more effective than other algorithms for this scheduling problem.

Managing Energy Plus Performance in Data Centers and Battery-Based Devices Using an Online Non-Clairvoyant Speed-Bounded Multiprocessor Scheduling

An efficient scheduling reduces the time required to process the jobs, and energy management decreases the service cost as well as increases the lifetime of a battery. A balanced trade-off between the energy consumed and processing time gives an ideal objective for scheduling jobs in data centers and battery based devices. An online multiprocessor scheduling multiprocessor with bounded speed (MBS) is proposed in this paper. The objective of MBS is to minimize the importance-based flow time plus energy (IbFt+E), wherein the jobs arrive over time and the job’s sizes are known only at completion time. Every processor can execute at a different speed, to reduce the energy consumption. MBS is using the tradition power function and bounded speed model. The functioning of MBS is evaluated by utilizing potential function analysis against an offline adversary. For processors m ≥ 2, MBS is O(1)-competitive. The working of a set of jobs is simulated to compare MBS with the best known non-clairvoyant scheduling. The comparative analysis shows that the MBS outperforms other algorithms. The competitiveness of MBS is the least to date.

Train-Scheduling Optimization Model for Railway Networks with Multiplatform Stations

This paper focuses on optimizing the schedule of trains on railway networks composed of busy complex stations. A mathematical formulation of this problem is provided as a Mixed Integer Linear Program (MILP). However, the creation of an optimal new timetable is an NP-hard problem; therefore, the MILP can be solved for easy cases, computation time being impractical for more complex examples. In these cases, a heuristic approach is provided that makes use of genetic algorithms to find a good solution jointly with heuristic techniques to generate an initial population. The algorithm was applied to a number of problem instances producing feasible, though not optimal, solutions in several seconds on a laptop, and compared to other proposals. Some improvements are suggested to obtain better results and further improve computation time. Rail transport is recognized as a sustainable and energy-efficient means of transport. Moreover, each freight train can take a large number of trucks off the roads, making them safer. Studies in this field can help to make railways more attractive to travelers by reducing operative cost, and increasing the number of services and their punctuality. To improve the transit system and service, it is necessary to build optimal train scheduling. There is an interest from the industry in automating the scheduling process. Fast computerized train scheduling, moreover, can be used to explore the effects of alternative draft timetables, operating policies, station layouts, and random delays or failures.

Particle Swarm Optimization and Tabu Search Hybrid Algorithm for Flexible Job Shop Scheduling Problem – Analysis of Test Results

The paper presents a hybrid metaheuristic algorithm, including a Particle Swarm Optimization (PSO) procedure and elements of Tabu Search (TS) metaheuristic. The novel algorithm is designed to solve Flexible Job Shop Scheduling Problems (FJSSP). Twelve benchmark test examples from different reference sources are experimentaly tested to demonstrate the performance of the algorithm. The obtained mean error for the deviation from optimality is 0.044%. The obtained test results are compared to the results in the reference sources and to the results by a genetic algorithm. The comparison illustrates the good performance of the proposed algorithm. Investigations on the base of test examples with a larger dimension will be carried out with the aim of further improvement of the algorithm and the quality of the test results.

Survey and Classification of Operational Control Problems in Discrete Event Logistics Systems (DELS)

This paper reviews and classifies literature on operational control of discrete event logistics systems (DELS). Operational control manipulates the flow of items through a DELS. Each control problem addressed in the surveyed literature is classified based on the control decision that the analysis model is formulated to support. These control decisions are defined by abstract functional definitions focusing on analysis model inputs, outputs, and variables. This classification of control problems shows that five kinds of atomic control decisions are needed to cover the literature, either by themselves or in combination. Standard functional definitions of operational control decisions enable discovery and interoperability of decision-support analysis models.

Scheduling multi-task jobs with extra utility in data centers

This paper investigates the problem of maximizing utility for job scheduling where each job consists of multiple tasks, each task has utility and each job also has extra utility if all tasks of that job are completed. We provide a 2-approximation algorithm for the single-machine case and a 2-approximation algorithm for the multi-machine problem. Both algorithms include two steps. The first step employs the Earliest Deadline First method to compute utility with only extra job utility, and it is proved that it obtains the optimal result for this sub-problem. The second step employs a Dynamic Programming method to compute utility without extra job utility, and it also derives the optimal result. An approximation result can then be obtained by combining the results of the two steps.

The checkpoint ordering problem

We suggest a new variant of a row layout problem: Find an ordering of n departments with given lengths such that the total weighted sum of their distances to a given checkpoint is minimized. The Checkpoint Ordering Problem (COP) is both of theoretical and practical interest. It has several applications and is conceptually related to some well-studied combinatorial optimization problems, namely the Single-Row Facility Layout Problem, the Linear Ordering Problem and a variant of parallel machine scheduling. In this paper we study the complexity of the (COP) and its special cases. The general version of the (COP) with an arbitrary but fixed number of checkpoints is NP-hard in the weak sense. We propose both a dynamic programming algorithm and an integer linear programming approach for the (COP) . Our computational experiments indicate that the (COP) is hard to solve in practice. While the run time of the dynamic programming algorithm strongly depends on the length of the departments, the integer linear programming approach is able to solve instances with up to 25 departments to optimality.

An Approach to Collaborative Scheduling Through Group Decision Support

The model we present supporting collaborative scheduling in complex dynamic manufacturing environments, considers the interaction between an agent-based scheduling module (ASM) and a group decision support module (GDSM). The ASM outputs a set of candidate scheduling solutions, each generated based on specific criteria and/or by a particular method. Scheduling is a multicriteria decision problem in practice where different schedulers may agree on key objectives but differ greatly on their relative importance in any given situation. Interaction among scheduling actors is supported by the GDSM selecting a scheduling solution.