Special Issue on Exact and Heuristic Scheduling Algorithms

Abstract

This special issue of Algorithms is a follow-up issue of an earlier one, entitled ‘Algorithms for Scheduling Problems’. In particular, the new issue is devoted to the development of exact and heuristic scheduling algorithms. Submissions were welcome both for traditional scheduling problems as well as for new practical applications. In the Call for Papers, we mentioned topics such as single-criterion and multi-criteria scheduling problems with additional constraints including setup times (costs), precedence constraints, batching (lot sizing), resource constraints as well as scheduling problems arising in emerging applications.

1. Introduction

Optimal scheduling is an important area of Operations Research and in particular of Decision Making. This research field covers a large variety of different solution approaches designed for particular problems. It is clear that efficient algorithms are highly desirable for large-size real-world scheduling problems. Due to the $NP$-hardness of the majority of scheduling problems, practitioners often prefer to use rather simple scheduling algorithms since large-size problems usually cannot be solved exactly in an acceptable time. However, fast heuristics may produce schedules of the function values that might be far away from the optimal ones.

This special issue contains both theoretical and practical aspects in the area of designing efficient exact and heuristic scheduling algorithms. We hope that the papers contained in this issue will stimulate researchers to find new practical directions for implementing their scheduling algorithms.

2. Main Results of the Special Issue

In response to the call for papers, we selected eight submissions for this special issue, all of which are of high quality, reflecting the interest in the area of developing exact and heuristic algorithms to solve real-world production planning and scheduling problems. As a rule, all submissions have been reviewed by three experts in the Discrete Optimization and Scheduling area. Subsequently, we survey the published papers in increasing order of their publication dates for this special issue.

The paper [1] was the first one accepted for this special issue. It deals with a real-world distribution problem arising in the vehicle production industry in Mexico. This problem includes both the loading and optimal routing of each auto-carrier, where both the capacity constraints and the time windows have to be taken into account. The authors suggest a two-stage heuristic algorithm. First, a route is constructed by an optimal insertion heuristic. Then a feasible loading is determined. For the computational experiments, two scenarios were generated with 11 different instances of the demand. Here one instance describes a real problem of a logistics company in Mexico. The algorithm allowed to obtain the routes and the loading of the vehicles for problems with 4400 vehicles and 44 dealerships considered. The results showed that the developed algorithm was successful in minimizing total traveling distance, loading/unloading operations and transportation costs.

The paper [2] is devoted to the heuristic solution of job shop scheduling problems with blocking constraints and minimization of total tardiness. This problem has many applications in manufacturing, but also in railway scheduling. Due to the hardness of the problem, the development of heuristics is of high relevance. In particular, a permutation-based heuristic is derived. The authors use three interchange- and shift-based transition schemes. However, typical neighborhoods applied to job shop problems often generate blocking infeasible solutions. Therefore, the core of this paper is to present two repair mechanisms that always generate blocking feasible neighbors. Characteristics for the complex neighborhoods such as the average distance of a neighbor are analyzed. The suggested neighborhoods are embedded into a simulated annealing algorithm. Detailed computational results have been given for the modified Lawrance instances with up to 30 jobs and 15 machines as well as for hard train inspired instances with up to 20 jobs and 11 machines. A computational comparison was made with the MIP formulation given in the paper [3]. It turned out that for small instances, the heuristic often obtained an optimal or near-optimal solution, while for larger instances several of the best known solutions by the MIP solver have been improved.

The paper [4] deals with scheduling jobs on a set of uniform parallel machines subject to given unavailability intervals with the objective to minimize the makespan. For this $NP$-hard problem, a new quadratic model is developed. In addition, the authors present a two-stage heuristic procedure. In the first phase, a modified Longest-Processing-Time rule is used to construct a schedule, which is then improved by pairwise interchanges of jobs between the machines. Computational results have been presented for instances with up to 2001 jobs and 1000 machines. The experiments showed that the quadratic model can solve small- and medium-size instances with roughly up to 140 jobs and 70 machines within a time limit of one hour. The heuristic algorithm presented in this paper was very fast and outperformed also an earlier heuristic from [5].

In the paper [6], some special cases of flow and job shop problems with so-called s-precedence constraints are addressed. This means that a task of a job cannot start before the task which precedes it has started. Polynomial algorithms are given for three special cases, namely a two-machine job shop problem with two jobs and allowed recirculation, the two-machine flow shop problem and an m-machine flow shop problem with two jobs, each with the objective to minimize the makespan. Finally, some special cases with open complexity status are mentioned.

The paper [7] analyzes the connections between usual scheduling criteria typically applied to flow shop problems like the makespan or idle time and customary shop floor performance measures such as work-in-progress or throughput. The authors setup a deep experimental analysis consisting in finding optimal or near-optimal schedules under several scheduling criteria and then investigating how these schedules behave in terms of different shop floor performance measures for several instances with different structures of the processing times. In particular, detailed computational results have been presented for instances with up to 200 jobs and 50 machines. It turned out that some of the scheduling criteria are poorly related to shop floor performance measures. In particular, the makespan performed only well with respect to throughput. On the other hand, the minimization of total completion time appeared to be better balanced in terms of shop floor performance. The paper finishes with suggesting some aspects for future work.

The paper [8] addresses a two-machine job shop scheduling problem, where the job duration may take any real value from a given segment. A stability approach [9] is applied to this uncertain scheduling problem. The scheduling decisions in the stability approach may consist of two successive phases: the first off-line phase, which is finished before starting the realization of a schedule, and the second on-line phase of scheduling, which is started with the beginning of the schedule realization. Using the information on the lower and upper bounds for each job duration available at the off-line phase, a scheduler can determine a minimal dominant set (DS) of schedules based on sufficient conditions for schedule dominance. The DS optimally covers all possible scenarios of the job durations in the sense that for each possible scenario, there exists at least one schedule in the DS which is optimal. Based on the DS, a scheduler can choose a schedule, which is optimal for the majority of possible scenarios. Polynomial algorithms have been developed for testing a set of conditions for schedule dominance. The conducted computational experiments on the randomly generated instances have shown the effectiveness of the developed algorithms. Most instances from the nine tested classes were optimally solved. If the maximum error was not greater than $20\%$, then more than $80\%$ of the tested instances were optimally solved. If the maximum error was equal to $50\%$, then $45\%$ of the tested instances from the nine classes were optimally solved.

The paper [10] deals with the Euclidean version of the traveling salesman problem (TSP), where the locations of the cities are points in the two-dimensional Euclidean space and the distances are Euclidean ones. For this problem, the authors suggest fast and easily implementable heuristics. They consist of three phases: construction, insertion and improvement. The first two phases run in $O\left(n\right)$ time with n being the number of points, and the number of improvement repetitions in the third phase is bounded by a small constant. The practical behavior of the suggested heuristics has been tested on 218 benchmark instances from several well-known libraries for TSP instances. In particular, the authors grouped the instances into small ones (up to 199 points), medium-size ones (between 200 and 9999 points) and large instances (between 10,000 and 250,000 points), and results for two very large instances with 498,378 and 744,410 points were also given. Although for most of the tested benchmark instances, the best known values have not been improved, nevertheless the computational times were smaller than the best known values earlier reported, and the heuristic is also efficient with respect to the required memory.

In the paper [11], a new mathematical model for a resource leveling problem with variable job durations is proposed, where the problem includes both scheduling and resource management decisions within a fixed planning horizon. The objective is to minimize total overload costs necessary for executing all jobs by the given deadline. In particular, the authors consider three different approaches for representing the scheduling constraints and decision variables, and they choose after some experiments a step (start/end) formulation of the scheduling constraints. Both the theoretical difference and relationships between the generalized modeling presented in this paper and the aggregated fraction model are discussed. The new formulation was compared to other models of the resource leveling problem from the literature on benchmark instances with up to 10 resource types and 30 jobs. Although the generalized modeling uses more variables and constraints, it nevertheless provided much better final solutions.