1 Introduction and Brief History

Scheduling theory is a field in operations research and discrete applied mathematics which is concerned with the optimal allocation of scarce resources (for instance, machines, processors, robots, operators, etc.) to activities over time, with the objective of optimizing one or several performance measures. The systematic study and efficient computer-aided solution of scheduling problems started about 70 years ago, being initiated by seminal papers by Johnson (1954) [1], Bellman (1956) [2], and Smith (1956) [3].

Since then a great diversity of scheduling models and solution techniques have been developed. Vast applications are found in industry, communications, transport, planning of military operations, healthcare, etc. Today, scheduling theory is a rapidly evolving area fruitfully contributing to computer science, artificial intelligence, industrial engineering and data science. The interested reader can find many nice examples of scheduling problems and elegant algorithms in surveys, textbooks, and monographs by Tanaev et al. [4], Lee et al. [5], Chen et al. [6], Pinedo [7], Blazewicz et al. [8], Levner [9], and Lenstra and Shmoys [10].

This paper describes the current state and prospects for the development of theoretical and practical research in the field of scheduling theory. The article is organized as follows. The second section discusses recent theoretical and algorithmic advances, including models and algorithms for multiagent scheduling, issues of integrating scheduling theory and queueing theory, etc. Section 3 is devoted to the description of scheduling models in artificial intelligence and scheduling of flying unmanned aerial vehicles and broadband wireless communication networks based on them. The final Sect. 4 briefly describes the directions for further research.

2 Recent Theoretical and Algorithmic Advances

2.1 Multiagent Schedulings

Research on multi-agent scheduling started about 20 years ago with papers by Baker and Smith [11] and Agnetis et al. [12] in which two-agent scheduling was introduced. In multiagent scheduling problems, activities (jobs) are allocated to resources (machines) similarly as in conventional single-agent single-objective scheduling problem but the major difference is that each job is controlled by an (usually human) agent who has his/her own criteria which may be competing and which is to be optimized by each agent.

Extensive surveys of recent multiagent scheduling models and algorithms are given in Agnetis et al. [13, 14], and Cheng et al. [15].

The multiagent scheduling, and, in particular, corresponding coordination mechanisms, are studied in a novel area in game theory known as job scheduling games, in which multiple users (agents) wish to utilize multiple machines, the incentive of each user being to optimize his/her own objective function [16].

2.2 Integrating Scheduling Theory and Queueing Theory

For many years queueing theory and scheduling theory have been developed independently and, as a consequence, have different performance measures, problem formulations and techniques. However, in recent years, the scheduling community has noticed that the long-term stochastic reasoning as studied in queueing theory can be usefully combined, both theoretically and practically, with short-term algorithmic reasoning studied in scheduling theory, and this fact can be used in applications when solving practical artificial intelligence and big data processing problems.

Interesting that as early as in 1956, Richard Bellman has noticed in [2]: “If we fix the [job] order and fasten our attention upon the distribution of idle times, the distribution of waiting times, and similar questions, we enter the domain of queuing theory (see Kendall, 1951 [49]). In this connection, we would like to point out that the explicit formulas of Johnson may be of some utility in determining limiting distributions”.

The queueing system consists of a single or several lines of waiting jobs (customers) and the available number of servers. Factors that are to be studied include: the line length(s), number of lines and the queue servicing discipline. Queue servicing discipline is the priority rule, similar to that in the scheduling theory, for determining the order of service to customers in waiting lines. Similar to what happens in the scheduling theory, the most common used are the following greedy priority rules: “first come, first served” (FCFS, FIFO); highest-profit or “best” customer first; largest orders first, longest wait-time first, and many others (see, for instance [8, 17,18,19].

An important aspect of the queueing system is the line structure. Analogous structures are investigated in the scheduling theory. However, different jobs in the queueing systems have different probabilistic characteristics and requirements for processing on different resources, and these characteristics often do not become known until the jobs arrive.

Some basic questions studied in queueing theory are beyond the scope of scheduling theory, like, e.g., “What is the average waiting time for customers in a line and in the system?”

In [20], Terekhov et al. took initial steps toward integrating queueing and scheduling for dynamic scheduling problems. The dynamic scheduling problems are characterized by a varying stream of jobs arriving stochastically over time. Each job requires a combination of resources, sequentially and/or in parallel, using different processing times. The existence of any particular job and its corresponding characteristics are not known until its arrival. However, the authors in [20] assumed, - as in queueing theory but not as in scheduling settings, that stochastic characteristics of the distribution of job arrivals are known. Jobs may require a complex routing through the available resources, which may be heterogeneous but with known and deterministic capacities. To solve a dynamic scheduling problem, the jobs must be assigned to appropriate resources and start times, respecting the resource and temporal constraints. As jobs arrive, there must be an online process to make decisions: it is not possible to solve the entire problem of-line.

Solving dynamic scheduling problems is challenging both due to the combinatorics of the interaction of jobs, resources, and time, and due to the stochastics: to make a decision, one can use only the information that is known with certainty at a decision point and the stochastic properties of scenarios that may occur in the future.

The authors of [20] showed that the well-known queueing theory notion of stability can be used to analyze periodic scheduling algorithms, and that, for each of the problems studied, periodic scheduling algorithms can be maximally stable, that is, no queueing policy or scheduling algorithm can allow the system to operate at a higher load or achieve a higher throughput. For one dynamic scheduling problem, the long-term stochastic reasoning of queueing can be combined with short-term combinatorial reasoning and produces a hybrid scheduling algorithm that achieves better performance than either queueing or scheduling approaches can provide if used alone.

These authors empirically demonstrated that for a comparatively simple dynamic flowshop, the use of combinatorial scheduling has a small impact on schedule quality. In contrast, for more complicated flexible queueing networks, a novel algorithm that combines long-term guidance from queueing theory with short-term decision making outperforms all other tested approaches.

Integrating Scheduling Theory and Queueing Theory has many yet unsolved challenges.

2.3 An Improved Near-Optimal Algorithm for the Traveling Salesman Problem

One of the fundamental problems in scheduling theory and discrete optimization is the traveling salesman problem (TSP), included in Karp’s initial list of 21 NP-complete problems [21]. In TSP we are given a set of n nodes (cities) V along with their pairwise symmetric distances, \(V \times V \rightarrow R \ge 0\). The goal is to find a Hamiltonian cycle of minimum cost. In the metric TSP problem, which we shall study in this section, the distances satisfy the triangle inequality.

First, we recall the classical Christofides–Serdyukov (CS) algorithm, also known in literature as the Christofides algorithm. Nicos Christofides and Anatoly Serdyukov have discovered it independently more than four decades ago, in [22] and [23], respectively (see also [24]). This algorithm finds approximate solutions to the metric TSP and guarantees that its solution is always within a factor of 3/2 of the optimal solution value. Such type algorithms are called near-optimal or with performance guarantees. Let \(G = (V, w)\) be an instance of the travelling salesman problem. That is, G is a complete graph on the set V of vertices, and the function w assigns a nonnegative real weight to every edge of G. The CS algorithm works as follows: Given an instance of the metric TSP, choose a minimum spanning tree and then add the minimum cost matching on the odd degree vertices of the tree. In spite of its simplicity, this algorithm is the best known to date polynomial time approximation algorithm with the performance guarantee for the metric traveling salesman problem. It is worth mentioning that there known the ‘complementary’ inapproximability results, for instance, it is NP-hard to approximate TSP within a factor of 123/122 [25].

For many years, nobody could improve the Christofides-Serdukov algorithmic result. And only quite recently, Karlin, Klein, and Gharan [26] introduced a novel approximation algorithm with a slightly better approximation ratio \(r = (3/2 - 10^{36})\).

Theorem 1

For some absolute constant \({>}{10^{36}}\), there is a randomized algorithm that outputs a tour with expected cost at most \(3/2 - \varepsilon \) times the cost of the optimum solution.

The method [26] closely follows the Christofides-Serdyukov’s algorithm, but uses a special randomly chosen tree rather than the minimum spanning tree. The authors note that their algorithm makes use of the Held-Karp relaxation [27]. They also remark that although their approximation factor is only slightly better than Christofides-Serdyukov’s, in their numerical experiments they did not discover any example where the approximation ratio of the algorithm exceeded 4/3 in expectation. This recent approach is an exciting and promising direction for further study and improvement of the classical Christofides-Serdyukov algorithm.

2.4 Almost-Optimal (Fully Polynomial Time Approximation) Scheduling Algorithms

An algorithm A for solving an optimization problem P (in particular, a scheduling problem) is called an almost optimal algorithm (or a fully polynomial-time approximation scheme FPTAS) if given an input I for P and an \(\varepsilon > 0\), the algorithm A finds in time polynomial in the size of I and in \(1/ \varepsilon \), a solution s for I that satisfies: \(| OPT(I) - f(s) | \le \varepsilon OPT(I)\), where OPT(I) is the optimal value of a solution for I.

A polynomial time approximation scheme PTAS is an algorithm which takes an instance of an optimization problem and a parameter \(\varepsilon > 0\) and, in polynomial time in the problem size, produces a solution that is within a factor \(1 + \varepsilon \) of being optimal for a minimization problem (or \(1 - \varepsilon \) for maximization problems). There exists dozens of different types of PTAS and FPTAS for many classes of scheduling problems (see Sahni [28], Babat [29], Gens and Levner [30], Lawler [31], Kovalyov et al. [32], Kovalyov and Kubiak [33], Woeginger [34], Hoesel.and Wagelmans [35], and references therein).

In this section, we give a brief description of several not-trivial FPTAS that have appeared in recent years. Liu and Wu [36] considered a scheduling problem in a flexible supply chain where jobs can be either processed in house, or outsourced to a third-party supplier with the goal of minimizing the sum of holding and delivery costs subject to an upper bound on the outsourcing cost. The problem with identical job processing times has been proved to be binary \(\mathcal {N}\mathcal {P}\)-hard; a fully polynomial time approximation scheme that runs in \(O(n^8(1/\varepsilon ^2))\) time has been known. This paper derives a faster FPTAS. Kacem and Levner [37] revisited he problem of scheduling a set of proportional deteriorating non-resumable jobs on a single machine subject to maintenance. The maintenance has to be started prior to a given deadline. The jobs as well as the maintenance are to be scheduled so that to minimize the total completion time. For this problem a new dynamic programming algorithm and a faster fully polynomial time approximation scheme are proposed improving a recent result by Luo and Chen [JIMO (2012), 8:2, 271–283]. Yin et al. [38] considered the problem of scheduling n independent and simultaneously available jobs without preemption on a single machine, where the machine has a fixed maintenance activity. The objective is to find the optimal job sequence to minimize the total amount of late work, where the late work of a job is the amount of processing of the job that is performed after its due date. The authors first discussed the approximability of the problem, then developed two pseudo-polynomial dynamic programming algorithms and constructed a fully polynomial-time approximation scheme for the problem. Finally, the authors performed extensive numerical studies to evaluate the performance of the proposed algorithms in practice. Zhao and Hsu [39] considered a single-machine scheduling problem in which the processing time of a job is a linear increasing function of its starting time. The objective is to minimize the weighted number of tardy jobs. A pseudo-polynomial dynamic programming algorithm and a new fully polynomial-time approximation scheme were proposed.

Halman et al. [40] presented a new framework for obtaining fully polynomial time approximation schemes for stochastic univariate dynamic programs with either convex or monotone single-period cost functions. This framework is workable for the stochastic scheduling problems and is developed through the establishment of two sets of computational rules, namely, the calculus of K-approximation functions and the calculus of K-approximation sets. Using this general framework, the novel FPTASs for several NP-hard scheduling problems were obtained.

More details on the properties of the FPTAS algorithms can be found in the tutorial [41].

3 Novel Models and Applications

3.1 Scheduling and Artificial Intelligence. Robots are Everywhere

In recent decades, there is a growing interest on scheduling problems for autonomous robots and robotic systems. There are numerous applications of artificial intelligence (AI) and smart robots in different industries, on the earth and in space (see, e.g., Pinedo [7], Blazewicz et al. [8], Levner et al. [9], Agnetis et al. [14]) and in communications and transport (Vishnevsky et al. [42, 43]). Modern flexible manufacturing systems are integrated with computer-controlled hoists, robots and other automatic devices. Robots have expanded production capabilities in manufacturing world making the technological processes faster, more efficient and precise than ever before. As larger and more complex robotic systems are implemented, more sophisticated scheduling models, methods and algorithms are required for performing and optimizing these processes.

More details on AI and robotic scheduling problems and algorithms are presented in [7,8,9, 42, 43].

3.2 Scheduling of Flying Unmanned Stations in Airborne Communication Networks

The unmanned aerial vehicle communication networks (UAV-CN) contain a set of unmanned aerial vehicles (UAVs) that constitute together a network which may be used for very many applications. The UAVs autonomously fly in 3-dimensional space in ad-hoc mode and carry out the communications and collaboration missions. The specificity of such communication networks is a high-speed of UAVs constituting the network nodes, which has a crucial impact on efficient routing. Another factor affecting the quality of communication service is the power issue that is limited and should be optimized during the design of the UAV-CNs.

In the last decade, unmanned aerial communication systems have emerged in different areas, such as military and police operations, search and evacuation emergency missions, detection of ecological disasters, border surveillance, traffic monitoring, etc. In these systems, unmanned aerial vehicles communicate with each other based on a flying network to provide services to customers such as live streaming, high-speed access point, etc. (see Vishnevsky et al. [42, 43]). The performance of UAV-CNs can be advantageous in emergency, for example, rescuing and searching people in areas where the conventional communication network is unavailable. In [44], the authors propose a method for detecting the coordinates of subscribers with the Wi-Fi signals generated from victims’ phones using a flying network for emergencies based on UAV swarms.

According to the IEEE classification (see [45, 46]), the wireless communication networks can be divided into two large domains: Infrastructure-based networks (IBN) and infrastructure-less networks (ILN), also called ad hoc networks.

Infrastructure-based network (IBN) has two subgroups, stationary and mobile. The stationary subgroup consists of stationary (static) base stations (BS) while the mobile subgroup consists of mobile nodes (MN) and master stations (MS) which are known as access points (AP).

The communication among MN is done with the help of access points which use different frequencies to establish the communication.

The infrastructure-less (ad hoc) networks are grouped, in turn, into wireless sensor network (WSN), wireless mesh networks (WMN), and mobile ad hoc networks (MANET). Next, the mobile ad hoc networks are classified into two sub groups: vehicular ad-hoc networks VANET and unmanned aerial vehicle communication networks UAV-CN.

As a typical fragment in novel applications, consider a perspective of exploiting classic scheduling models and methods for efficient scheduling of a flying UAV-CNs with the minimum number of UAVs.

We suggest to use the extension of the Kats-Levner model [47, 48] for defining the minimum number of vehicles to meet a fixed schedule. In a new setting, we have the following problem. We study a cyclic process in which a set of several sensors perform m operations of data collection. A number of flying unmanned stations (drones) are used to transfer information of sensors from one sensor to another. The durations of data collecting and data transfers are known. The problem that has the key performance measure, the number of drones to be used. The aim is to find the minimum number of drones needed to meet a given cyclic schedule, for a fixed cycle length.

If the transfer times in the considered UAV (drone) scheduling problem satisfy the triangle inequality then the minimal number of UAVs needed to meet a given cyclic schedule of a fixed period length, is equal to the optimum solution of the \(m \times m\) assignment problem. The complexity of the algorithm is \(O(m^3)\), independently of the range within which the cycle length value may vary. The problem has several practical modifications (see, for instance, [47, 48]).

4 Concluding Remark: A Look to the Future

There exist a number of related attractive fields which are not covered in this survey, for instance, knowledge-based scheduling, real time scheduling, scheduling in cloud computing, and scheduling with communication delays. They will be overviewed in our future work.