Editorial

4 pages, 171 KiB

Open AccessEditorial

Special Issue on Exact and Heuristic Scheduling Algorithms

by Frank Werner, Larysa Burtseva and Yuri N. Sotskov

Algorithms 2020, 13(1), 9; https://0-doi-org.brum.beds.ac.uk/10.3390/a13010009 - 25 Dec 2019

Cited by 5 | Viewed by 3418

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 [...] Read more.

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. Full article

(This article belongs to the Special Issue Exact and Heuristic Scheduling Algorithms)

Research

Jump to: Editorial

15 pages, 349 KiB

Open AccessArticle

A Generalized MILP Formulation for the Period-Aggregated Resource Leveling Problem with Variable Job Duration

by Ilia Tarasov, Alain Haït and Olga Battaïa

Algorithms 2020, 13(1), 6; https://0-doi-org.brum.beds.ac.uk/10.3390/a13010006 - 23 Dec 2019

Cited by 7 | Viewed by 3554

Abstract

We study a resource leveling problem with variable job duration. The considered problem includes both scheduling and resource management decisions. The planning horizon is fixed and separated into a set of time periods of equal length. There are several types of resources and [...] Read more.

We study a resource leveling problem with variable job duration. The considered problem includes both scheduling and resource management decisions. The planning horizon is fixed and separated into a set of time periods of equal length. There are several types of resources and their amount varies from one period to another. There is a set of jobs. For each job, a fixed volume of work has to be completed without any preemption while using different resources. If necessary, extra resources can be used at additional costs during each time period. The optimization goal is to minimize the total overload costs required for the execution of all jobs by the given deadline. The decision variables specify the starting time of each job, the duration of the job and the resource amount assigned to the job during each period (it may vary over periods). We propose a new generalized mathematical formulation for this optimization problem. The formulation is compared with existing approaches from the literature. Theoretical study and computational experiments show that our approach provides more flexible resource allocation resulting in better final solutions. Full article

(This article belongs to the Special Issue Exact and Heuristic Scheduling Algorithms)

► Show Figures

Figure 1

30 pages, 576 KiB

Open AccessArticle

Simple Constructive, Insertion, and Improvement Heuristics Based on the Girding Polygon for the Euclidean Traveling Salesman Problem

by Víctor Pacheco-Valencia, José Alberto Hernández, José María Sigarreta and Nodari Vakhania

Algorithms 2020, 13(1), 5; https://0-doi-org.brum.beds.ac.uk/10.3390/a13010005 - 21 Dec 2019

Cited by 9 | Viewed by 4754

Abstract

The Traveling Salesman Problem (TSP) aims at finding the shortest trip for a salesman, who has to visit each of the locations from a given set exactly once, starting and ending at the same location. Here, we consider the Euclidean version of the [...] Read more.

The Traveling Salesman Problem (TSP) aims at finding the shortest trip for a salesman, who has to visit each of the locations from a given set exactly once, starting and ending at the same location. Here, we consider the Euclidean version of the problem, in which the locations are points in the two-dimensional Euclidean space and the distances are correspondingly Euclidean distances. We propose simple, fast, and easily implementable heuristics that work well, in practice, for large real-life problem instances. The algorithm works on three phases, the constructive, the insertion, and the improvement phases. The first two phases run in time

O (n^{2})

and the number of repetitions in the improvement phase, in practice, is bounded by a small constant. We have tested the practical behavior of our heuristics on the available benchmark problem instances. The approximation provided by our algorithm for the tested benchmark problem instances did not beat best known results. At the same time, comparing the CPU time used by our algorithm with that of the earlier known ones, in about 92% of the cases our algorithm has required less computational time. Our algorithm is also memory efficient: for the largest tested problem instance with 744,710 cities, it has used about 50 MiB, whereas the average memory usage for the remained 217 instances was 1.6 MiB. Full article

(This article belongs to the Special Issue Exact and Heuristic Scheduling Algorithms)

► Show Figures

Figure 1

45 pages, 620 KiB

Open AccessArticle

Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations

by Yuri N. Sotskov, Natalja M. Matsveichuk and Vadzim D. Hatsura

Algorithms 2020, 13(1), 4; https://0-doi-org.brum.beds.ac.uk/10.3390/a13010004 - 20 Dec 2019

Cited by 9 | Viewed by 5258

Abstract

We study two-machine shop-scheduling problems provided that lower and upper bounds on durations of n jobs are given before scheduling. An exact value of the job duration remains unknown until completing the job. The objective is to minimize the makespan (schedule length). We [...] Read more.

We study two-machine shop-scheduling problems provided that lower and upper bounds on durations of n jobs are given before scheduling. An exact value of the job duration remains unknown until completing the job. The objective is to minimize the makespan (schedule length). We address the issue of how to best execute a schedule if the job duration may take any real value from the given segment. Scheduling decisions may consist of two phases: an off-line phase and an on-line phase. Using 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 of schedules (DS) based on sufficient conditions for schedule domination. The DS optimally covers all possible realizations (scenarios) of the uncertain job durations in the sense that, for each possible scenario, there exists at least one schedule in the DS which is optimal. The DS enables a scheduler to quickly make an on-line scheduling decision whenever additional information on completing jobs is available. A scheduler can choose a schedule which is optimal for the most possible scenarios. We developed algorithms for testing a set of conditions for a schedule dominance. These algorithms are polynomial in the number of jobs. Their time complexity does not exceed

O (n^{2})

. Computational experiments have shown the effectiveness of the developed algorithms. If there were no more than 600 jobs, then all 1000 instances in each tested series were solved in one second at most. An instance with 10,000 jobs was solved in 0.4 s on average. The most instances from nine tested classes were optimally solved. If the maximum relative error of the job duration was not greater than

20 %

, then more than

80 %

of the tested instances were optimally solved. If the maximum relative error was equal to

50 %

, then

45 %

of the tested instances from the nine classes were optimally solved. Full article

(This article belongs to the Special Issue Exact and Heuristic Scheduling Algorithms)

► Show Figures

Figure 1

21 pages, 572 KiB

Open AccessFeature PaperArticle

Linking Scheduling Criteria to Shop Floor Performance in Permutation Flowshops

by Jose M. Framinan and Rainer Leisten

Algorithms 2019, 12(12), 263; https://0-doi-org.brum.beds.ac.uk/10.3390/a12120263 - 07 Dec 2019

Cited by 5 | Viewed by 3310

Abstract

The goal of manufacturing scheduling is to allocate a set of jobs to the machines in the shop so these jobs are processed according to a given criterion (or set of criteria). Such criteria are based on properties of the jobs to be [...] Read more.

The goal of manufacturing scheduling is to allocate a set of jobs to the machines in the shop so these jobs are processed according to a given criterion (or set of criteria). Such criteria are based on properties of the jobs to be scheduled (e.g., their completion times, due dates); so it is not clear how these (short-term) criteria impact on (long-term) shop floor performance measures. In this paper, we analyse the connection between the usual scheduling criteria employed as objectives in flowshop scheduling (e.g., makespan or idle time), and customary shop floor performance measures (e.g., work-in-process and throughput). Two of these linkages can be theoretically predicted (i.e., makespan and throughput as well as completion time and average cycle time), and the other such relationships should be discovered on a numerical/empirical basis. In order to do so, we set up an experimental analysis consisting in finding optimal (or good) schedules under several scheduling criteria, and then computing how these schedules perform in terms of the different shop floor performance measures for several instance sizes and for different structures of processing times. Results indicate that makespan only performs well with respect to throughput, and that one formulation of idle times obtains nearly as good results as makespan, while outperforming it in terms of average cycle time and work in process. Similarly, minimisation of completion time seems to be quite balanced in terms of shop floor performance, although it does not aim exactly at work-in-process minimisation, as some literature suggests. Finally, the experiments show that some of the existing scheduling criteria are poorly related to the shop floor performance measures under consideration. These results may help to better understand the impact of scheduling on flowshop performance, so scheduling research may be more geared towards shop floor performance, which is sometimes suggested as a cause for the lack of applicability of some scheduling models in manufacturing. Full article

(This article belongs to the Special Issue Exact and Heuristic Scheduling Algorithms)

► Show Figures

Figure 1

12 pages, 630 KiB

Open AccessFeature PaperArticle

Some Results on Shop Scheduling with S-Precedence Constraints among Job Tasks

by Alessandro Agnetis, Fabrizio Rossi and Stefano Smriglio

Algorithms 2019, 12(12), 250; https://0-doi-org.brum.beds.ac.uk/10.3390/a12120250 - 25 Nov 2019

Cited by 5 | Viewed by 3502

Abstract

We address some special cases of job shop and flow shop scheduling problems with s-precedence constraints. Unlike the classical setting, in which precedence constraints among the tasks of a job are finish–start, here the task of a job cannot start before the task [...] Read more.

We address some special cases of job shop and flow shop scheduling problems with s-precedence constraints. Unlike the classical setting, in which precedence constraints among the tasks of a job are finish–start, here the task of a job cannot start before the task preceding it has started. We give polynomial exact algorithms for the following problems: a two-machine job shop with two jobs when recirculation is allowed (i.e., jobs can visit the same machine many times), a two-machine flow shop, and an m-machine flow shop with two jobs. We also point out some special cases whose complexity status is open. Full article

(This article belongs to the Special Issue Exact and Heuristic Scheduling Algorithms)

► Show Figures

Figure 1

11 pages, 362 KiB

Open AccessArticle

Modeling and Solving Scheduling Problem with m Uniform Parallel Machines Subject to Unavailability Constraints

by Jihene Kaabi

Algorithms 2019, 12(12), 247; https://0-doi-org.brum.beds.ac.uk/10.3390/a12120247 - 21 Nov 2019

Cited by 4 | Viewed by 3614

Abstract

The problem investigated in this paper is scheduling on uniform parallel machines, taking into account that machines can be periodically unavailable during the planning horizon. The objective is to determine planning for job processing so that the makespan is minimal. The problem is [...] Read more.

The problem investigated in this paper is scheduling on uniform parallel machines, taking into account that machines can be periodically unavailable during the planning horizon. The objective is to determine planning for job processing so that the makespan is minimal. The problem is known to be NP-hard. A new quadratic model was developed. Because of the limitation of the aforementioned model in terms of problem sizes, a novel algorithm was developed to tackle big-sized instances. This consists of mainly two phases. The first phase generates schedules using a modified Largest Processing Time (

L P T

)-based procedure. Then, theses schedules are subject to further improvement during the second phase. This improvement is obtained by simultaneously applying pairwise job interchanges between machines. The proposed algorithm and the quadratic model were implemented and tested on variously sized problems. Computational results showed that the developed quadratic model could optimally solve small- to medium-sized problem instances. However, the proposed algorithm was able to optimally solve large-sized problems in a reasonable time. Full article

(This article belongs to the Special Issue Exact and Heuristic Scheduling Algorithms)

► Show Figures

Figure 1

28 pages, 489 KiB

Open AccessArticle

On Neighborhood Structures and Repair Techniques for Blocking Job Shop Scheduling Problems

by Julia Lange and Frank Werner

Algorithms 2019, 12(11), 242; https://0-doi-org.brum.beds.ac.uk/10.3390/a12110242 - 12 Nov 2019

Cited by 11 | Viewed by 4005

Abstract

The job shop scheduling problem with blocking constraints and total tardiness minimization represents a challenging combinatorial optimization problem of high relevance in production planning and logistics. Since general-purpose solution approaches struggle with finding even feasible solutions, a permutation-based heuristic method is proposed here, [...] Read more.

The job shop scheduling problem with blocking constraints and total tardiness minimization represents a challenging combinatorial optimization problem of high relevance in production planning and logistics. Since general-purpose solution approaches struggle with finding even feasible solutions, a permutation-based heuristic method is proposed here, and the applicability of basic scheduling-tailored mechanisms is discussed. The problem is tackled by a local search framework, which relies on interchange- and shift-based operators. Redundancy and feasibility issues require advanced transformation and repairing schemes. An analysis of the embedded neighborhoods shows beneficial modes of implementation on the one hand and structural difficulties caused by the blocking constraints on the other hand. The applied simulated annealing algorithm generates good solutions for a wide set of benchmark instances. The computational results especially highlight the capability of the permutation-based method in constructing feasible schedules of valuable quality for instances of critical size and support future research on hybrid solution techniques. Full article

(This article belongs to the Special Issue Exact and Heuristic Scheduling Algorithms)

► Show Figures

Figure 1

19 pages, 1537 KiB

Open AccessArticle

A Heuristic Algorithm for the Routing and Scheduling Problem with Time Windows: A Case Study of the Automotive Industry in Mexico

by Marco Antonio Juárez Pérez, Rodolfo Eleazar Pérez Loaiza, Perfecto Malaquias Quintero Flores, Oscar Atriano Ponce and Carolina Flores Peralta

Algorithms 2019, 12(5), 111; https://0-doi-org.brum.beds.ac.uk/10.3390/a12050111 - 25 May 2019

Cited by 8 | Viewed by 5794

Abstract

This paper investigates a real-world distribution problem arising in the vehicle production industry, particularly in a logistics company, in which cars and vans must be loaded on auto-carriers and then delivered to dealerships. A solution to the problem involves the loading and optimal [...] Read more.

This paper investigates a real-world distribution problem arising in the vehicle production industry, particularly in a logistics company, in which cars and vans must be loaded on auto-carriers and then delivered to dealerships. A solution to the problem involves the loading and optimal routing, without violating the capacity and time window constraints for each auto-carrier. A two-phase heuristic algorithm was implemented to solve the problem. In the first phase the heuristic builds a route with an optimal insertion procedure, and in the second phase the determination of a feasible loading. The experimental results show that the purposed algorithm can be used to tackle the transportation problem in terms of minimizing total traveling distance, loading/unloading operations and transportation costs, facilitating a decision-making process for the logistics company. Full article

(This article belongs to the Special Issue Exact and Heuristic Scheduling Algorithms)

► Show Figures

Figure 1

Journal Menu

Journal Browser

Exact and Heuristic Scheduling Algorithms

Share This Special Issue

Special Issue Editors

Special Issue Information

Keywords

Published Papers (9 papers)

Editorial

Research

Further Information

Guidelines

MDPI Initiatives

Follow MDPI