Special Issue “Recent Advances of Discrete Optimization and Scheduling”

This Special Issue of the journal Mathematics is dedicated to new results on the topic of discrete optimization and scheduling. We particularly invited submissions for articles aimed at solving problems in practical applications, e.g., optimization problems related to the management of medical institutions, cargo transportation, or production planning, to name a few. Both structural investigations as well as investigations on algorithm efficiency were welcome.

After a careful peer-review process, 10 papers were selected for this Issue, which represent a broad spectrum of research fields in discrete optimization and scheduling. As a rule, all submissions were reviewed by two or more experts from the corresponding area. Subsequently, the papers were then surveyed in increasing order of their publication dates.

The first accepted paper, written by Jang et al., deals with a batch loading and scheduling problem on parallel machines with the objective to minimize the makespan. In particular, the authors suggest a three-stage ant colony algorithm which can find optimal solutions for instances of small size. For large-sized instances, the algorithm was found to be superior to a genetic algorithm as well as a particle swarm algorithm.

The second paper of this Issue, written by Karunanidy et al., suggests a novel Java macaque algorithm, which mimics the natural behaviour of the Java macaque monkeys and uses a promising social hierarchy-based selection process. The algorithm presented in this paper is extensively tested on various benchmark functions for a continuous optimization problem and on the traveling salesman problem as a frequently considered discrete optimization problem. The presented algorithm was found to be efficient compared to existing dominant optimization algorithms.

In contribution 3, Lazarev at al. conducted a study concerning scheduling surgeries in operating rooms. They suggested a model that uses a variation of the bin packing problem with the primary goal of increasing patient throughput. Since the suggested mixed-integer model is computationally extensive, two approximation algorithms based on decomposition are also presented. Using the Gurobi solver, experiments were performed using real historical data for surgeries in a Russian neurosurgical center.

Makarovskikh and Panyukov carried out research pertaining to routing problems on plane graphs with the goal to solve the industrial control problems of cutting machines. Polynomial algorithms were developed to determine listed routes with the minimum number of covering paths and the minimum length of transitions, between the end of the current path and the beginning of the next path. It was concluded that the obtained solutions can improve the quality of the technological preparation of such cutting processes in CAD/CAM systems.

The work of Afraimovich and Emelin concerns the three-index axial assignment problem, which is NP-hard. The problem of combining feasible solutions is investigated, and approaches for the solution of such combination problems are considered. It is proven that the resulting problem is already NP-hard in the case of combining four solutions.

The sixth published paper by Galuzin et al. presents an autonomous digital twin of an enterprise with the goal to provide the knowledge-based multi-agent adaptive allocation, scheduling, optimization, monitoring, and control of tasks and resources in real time. Formalized ontological and multi-agent models for developing such digital twins are presented. The developed approaches and toolset were found to be successful in terms of efficiency as well as savings in time and delivery costs.

Behmanesh-Fard et al. present a mathematical model for symbolic pole/zero simplification in operational transconductance amplifiers. After solving the circuit symbolically and applying an improved root-splitting method, a hybrid algorithm is used and combined with a simulated annealing metaheuristic method for the simplification of the derived symbolic roots. The developed approach is tested on three amplifiers, and the approach determines accurate simplified expressions with low complexity.

In the next paper, Chao and Lin attempt to solve a single-machine scheduling problem with shared common setup operations resulting from a software test. The authors suggest sequence-based and position-based integer programming models as well as a branch and bound algorithm. To obtain an upper bound for the latter algorithm, an ant colony algorithm is used. Detailed numerical results for a dataset with up to 50 jobs and 45 setup operations are presented.

Shen and Zhang present a novel method to construct so-called Goethals–Seidel sequences with special structures. They present significant results that allow users to potentially construct all of such sequences more efficiently. Moreover, some of their examples are considered to verify the obtained theoretical results.

In contribution 10, as the last accepted paper, Lazarev et al. target the single-machine scheduling problem so as to minimize total weighted completion times. They assume that the objective coefficients are unknown, but the set of optimal schedules is given. The problem can be reduced to a system of linear inequalities for the coefficients. For the case of simultaneous job release times, the authors present an algorithm for solving this system, which is the base for a polynomial algorithm to find the weight coefficients belonging to the given optimal schedules.

It is our pleasure to thank all authors for submitting their recent works, all reviewers for their timely and insightful reports, and the staff of the Editorial Office for their support in preparing this Issue. We hope that the readers of this Issue will find stimulating ideas to initiate new research in this challenging research field.