Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
4.1
1.8
Journals
Algorithms
Special Issues
Algorithms for Scheduling Problems
share announcement

Algorithms for Scheduling Problems

A special issue of Algorithms (ISSN 1999-4893).

Deadline for manuscript submissions: closed (28 February 2018) | Viewed by 71917

Printed Edition Available!
A printed edition of this Special Issue is available here.

Special Issue Editors

Dr. Larysa Burtseva

E-Mail Website
Co-Guest Editor
1. CICESE Research Center, carr. Tijuana-Ensenada 3918, Ensenada 22860, BC, Mexico
2. Ivannikov Institute for System Programming, RAS Moskow, Alexander Solzhenitsyn Street, 25, 109004 Moskow, Russia
Interests: multi-objective resource optimization; security, uncertainty, dynamic scheduling; adaptive resource allocation
Prof. Dr. Frank Werner

E-Mail Website
Guest Editor
Faculty of Mathematics, Otto-von-Guericke-University, P.O. Box 4120, D-39016 Magdeburg, Germany
Interests: scheduling, in particular development of exact and approximate algorithms; stability investigations is discrete optimization; scheduling with interval processing times; complexity investigations for scheduling problems; train scheduling; graph theory; logistics; supply chains; packing; simulation and applications
Special Issues, Collections and Topics in MDPI journals
Prof. Dr. Yuri Sotskov

E-Mail
Co-Guest Editor
United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova Street 6, 220012 Minsk, Belarus
Interests: discrete optimization; scheduling; graph theory; uncertainty

Special Issue Information

Dear Colleagues,

We invite you to submit your latest research in the area of the development of scheduling algorithms to this Special Issue, “Algorithms for Scheduling Problems”. We are looking for new and innovative approaches for solving scheduling problems exactly or approximately. High-quality papers are solicited to address both theoretical and practical issues of scheduling algorithms. Submissions are welcome both for traditional scheduling problems, as well as new applications. Potential topics include, but are not limited to, sequencing in single- and multi-stage systems with additional constraints such as setup times or costs, precedence constraints, batching/lot sizing, resource constraints, etc., and single- or multi-criteria objectives as well as to a broad spectrum of scheduling problems in emerging applications, such as sports, healthcare, or energy management.    

Prof. Dr. Frank Werner
Dr. Larysa Burtseva
Prof. Dr. Yuri Sotskov
Guest Editors

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Algorithms is an international peer-reviewed open access monthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 1600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Keywords

  • Complex Scheduling Problems
  • Scheduling Problems in Segments of a Supply Chain
  • Scheduling Problems in Logistics, Transport, Timetabling, Sports, Healthcare, Engineering, Energy Management etc.
  • Vehicle Routing
  • Scheduling under Uncertainty
  • Scheduling under Resource Constraints
  • Just-in-Time Scheduling
  • Assembly Scheduling
  • Agent Based Scheduling
  • Real-Time Scheduling
  • Scheduling Heuristics and Metaheuristics
  • Evolutionary Algorithms
  • Approximation Algorithms
  • Enumerative Algorithms
  • Complexity Issues

Benefits of Publishing in a Special Issue

  • Ease of navigation: Grouping papers by topic helps scholars navigate broad scope journals more efficiently.
  • Greater discoverability: Special Issues support the reach and impact of scientific research. Articles in Special Issues are more discoverable and cited more frequently.
  • Expansion of research network: Special Issues facilitate connections among authors, fostering scientific collaborations.
  • External promotion: Articles in Special Issues are often promoted through the journal's social media, increasing their visibility.
  • e-Book format: Special Issues with more than 10 articles can be published as dedicated e-books, ensuring wide and rapid dissemination.

Further information on MDPI's Special Issue polices can be found here.

Published Papers (12 papers)

Download All Papers
Order results
Result details
Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:

Editorial

Jump to: Research

4 pages, 157 KiB  
Editorial
Special Issue on Algorithms for Scheduling Problems
by Frank Werner, Larysa Burtseva and Yuri N. Sotskov
Algorithms 2018, 11(6), 87; https://doi.org/10.3390/a11060087 - 20 Jun 2018
Cited by 4 | Viewed by 4582
Abstract
This special issue of Algorithms is devoted to the development of scheduling algorithms based on innovative approaches for solving hard scheduling problems either exactly or approximately. Submissions were welcome both for traditional scheduling problems as well as for new practical applications. The main [...] Read more.
This special issue of Algorithms is devoted to the development of scheduling algorithms based on innovative approaches for solving hard scheduling problems either exactly or approximately. Submissions were welcome both for traditional scheduling problems as well as for new practical applications. The main topics include sequencing and scheduling with additional constraints (setup times or costs, precedence constraints, resource constraints, and batch production environment) and production planning and scheduling problems arising in real-world applications. Full article
(This article belongs to the Special Issue Algorithms for Scheduling Problems)

Research

Jump to: Editorial

16 pages, 293 KiB  
Article
Scheduling a Single Machine with Primary and Secondary Objectives
by Nodari Vakhania
Algorithms 2018, 11(6), 80; https://doi.org/10.3390/a11060080 - 5 Jun 2018
Cited by 6 | Viewed by 4023
Abstract
We study a scheduling problem in which jobs with release times and due dates are to be processed on a single machine. With the primary objective to minimize the maximum job lateness, the problem is strongly NP-hard. We describe a general algorithmic scheme [...] Read more.
We study a scheduling problem in which jobs with release times and due dates are to be processed on a single machine. With the primary objective to minimize the maximum job lateness, the problem is strongly NP-hard. We describe a general algorithmic scheme to minimize the maximum job lateness, with the secondary objective to minimize the maximum job completion time. The problem of finding the Pareto-optimal set of feasible solutions with these two objective criteria is strongly NP-hard. We give the dominance properties and conditions when the Pareto-optimal set can be formed in polynomial time. These properties, together with our general framework, provide the theoretical background, so that the basic framework can be expanded to (exponential-time) implicit enumeration algorithms and polynomial-time approximation algorithms (generating the Pareto sub-optimal frontier with a fair balance between the two objectives). Some available in the literature experimental results confirm the practical efficiency of the proposed framework. Full article
(This article belongs to the Special Issue Algorithms for Scheduling Problems)
►▼ Show Figures

Figure 1

13 pages, 2000 KiB  
Article
PHEFT: Pessimistic Image Processing Workflow Scheduling for DSP Clusters
by Alexander Yu. Drozdov, Andrei Tchernykh, Sergey V. Novikov, Victor E. Vladislavlev and Raul Rivera-Rodriguez
Algorithms 2018, 11(5), 76; https://doi.org/10.3390/a11050076 - 22 May 2018
Cited by 4 | Viewed by 5169
Abstract
We address image processing workflow scheduling problems on a multicore digital signal processor cluster. We present an experimental study of scheduling strategies that include task labeling, prioritization, resource selection, and digital signal processor scheduling. We apply these strategies in the context of executing [...] Read more.
We address image processing workflow scheduling problems on a multicore digital signal processor cluster. We present an experimental study of scheduling strategies that include task labeling, prioritization, resource selection, and digital signal processor scheduling. We apply these strategies in the context of executing the Ligo and Montage applications. To provide effective guidance in choosing a good strategy, we present a joint analysis of three conflicting goals based on performance degradation. A case study is given, and experimental results demonstrate that a pessimistic scheduling approach provides the best optimization criteria trade-offs. The Pessimistic Heterogeneous Earliest Finish Time scheduling algorithm performs well in different scenarios with a variety of workloads and cluster configurations. Full article
(This article belongs to the Special Issue Algorithms for Scheduling Problems)
►▼ Show Figures

Figure 1

23 pages, 13706 KiB  
Article
Hybrid Flow Shop with Unrelated Machines, Setup Time, and Work in Progress Buffers for Bi-Objective Optimization of Tortilla Manufacturing
by Victor Hugo Yaurima-Basaldua, Andrei Tchernykh, Francisco Villalobos-Rodríguez and Ricardo Salomon-Torres
Algorithms 2018, 11(5), 68; https://doi.org/10.3390/a11050068 - 9 May 2018
Cited by 8 | Viewed by 7304
Abstract
We address a scheduling problem in an actual environment of the tortilla industry. Since the problem is NP hard, we focus on suboptimal scheduling solutions. We concentrate on a complex multistage, multiproduct, multimachine, and batch production environment considering completion time and energy consumption [...] Read more.
We address a scheduling problem in an actual environment of the tortilla industry. Since the problem is NP hard, we focus on suboptimal scheduling solutions. We concentrate on a complex multistage, multiproduct, multimachine, and batch production environment considering completion time and energy consumption optimization criteria. The production of wheat-based and corn-based tortillas of different styles is considered. The proposed bi-objective algorithm is based on the known Nondominated Sorting Genetic Algorithm II (NSGA-II). To tune it up, we apply statistical analysis of multifactorial variance. A branch and bound algorithm is used to assert obtained performance. We show that the proposed algorithms can be efficiently used in a real production environment. The mono-objective and bi-objective analyses provide a good compromise between saving energy and efficiency. To demonstrate the practical relevance of the results, we examine our solution on real data. We find that it can save 48% of production time and 47% of electricity consumption over the actual production. Full article
(This article belongs to the Special Issue Algorithms for Scheduling Problems)
►▼ Show Figures

Figure 1

20 pages, 358 KiB  
Article
Single Machine Scheduling Problem with Interval Processing Times and Total Completion Time Objective
by Yuri N. Sotskov and Natalja G. Egorova
Algorithms 2018, 11(5), 66; https://doi.org/10.3390/a11050066 - 7 May 2018
Cited by 11 | Viewed by 4878
Abstract
We consider a single machine scheduling problem with uncertain durations of the given jobs. The objective function is minimizing the sum of the job completion times. We apply the stability approach to the considered uncertain scheduling problem using a relative perimeter of the [...] Read more.
We consider a single machine scheduling problem with uncertain durations of the given jobs. The objective function is minimizing the sum of the job completion times. We apply the stability approach to the considered uncertain scheduling problem using a relative perimeter of the optimality box as a stability measure of the optimal job permutation. We investigated properties of the optimality box and developed algorithms for constructing job permutations that have the largest relative perimeters of the optimality box. Computational results for constructing such permutations showed that they provided the average error less than 0 . 74 % for the solved uncertain problems. Full article
(This article belongs to the Special Issue Algorithms for Scheduling Problems)
►▼ Show Figures

Figure 1

20 pages, 3954 KiB  
Article
Optimal Control Algorithms and Their Analysis for Short-Term Scheduling in Manufacturing Systems
by Boris Sokolov, Alexandre Dolgui and Dmitry Ivanov
Algorithms 2018, 11(5), 57; https://doi.org/10.3390/a11050057 - 3 May 2018
Cited by 20 | Viewed by 6476
Abstract
Current literature presents optimal control computational algorithms with regard to state, control, and conjunctive variable spaces. This paper first analyses the advantages and limitations of different optimal control computational methods and algorithms which can be used for short-term scheduling. Second, it develops an [...] Read more.
Current literature presents optimal control computational algorithms with regard to state, control, and conjunctive variable spaces. This paper first analyses the advantages and limitations of different optimal control computational methods and algorithms which can be used for short-term scheduling. Second, it develops an optimal control computational algorithm that allows for the solution of short-term scheduling in an optimal manner. Moreover, qualitative and quantitative analysis of the manufacturing system scheduling problem is presented. Results highlight computer experiments with a scheduling software prototype as well as potential future research avenues. Full article
(This article belongs to the Special Issue Algorithms for Scheduling Problems)
►▼ Show Figures

Figure 1

18 pages, 1428 KiB  
Article
A Heuristic Approach to Solving the Train Traffic Re-Scheduling Problem in Real Time
by Omid Gholami and Johanna Törnquist Krasemann
Algorithms 2018, 11(4), 55; https://doi.org/10.3390/a11040055 - 21 Apr 2018
Cited by 7 | Viewed by 6949
Abstract
Effectiveness in managing disturbances and disruptions in railway traffic networks, when they inevitably do occur, is a significant challenge, both from a practical and theoretical perspective. In this paper, we propose a heuristic approach for solving the real-time train traffic re-scheduling problem. This [...] Read more.
Effectiveness in managing disturbances and disruptions in railway traffic networks, when they inevitably do occur, is a significant challenge, both from a practical and theoretical perspective. In this paper, we propose a heuristic approach for solving the real-time train traffic re-scheduling problem. This problem is here interpreted as a blocking job-shop scheduling problem, and a hybrid of the mixed graph and alternative graph is used for modelling the infrastructure and traffic dynamics on a mesoscopic level. A heuristic algorithm is developed and applied to resolve the conflicts by re-timing, re-ordering, and locally re-routing the trains. A part of the Southern Swedish railway network from Karlskrona centre to Malmö city is considered for an experimental performance assessment of the approach. The network consists of 290 block sections, and for a one-hour time horizon with around 80 active trains, the algorithm generates a solution in less than ten seconds. A benchmark with the corresponding mixed-integer program formulation, solved by commercial state-of-the-art solver Gurobi, is also conducted to assess the optimality of the generated solutions. Full article
(This article belongs to the Special Issue Algorithms for Scheduling Problems)
►▼ Show Figures

Figure 1

18 pages, 3782 KiB  
Article
Dual Market Facility Network Design under Bounded Rationality
by D. G. Mogale, Geet Lahoti, Shashi Bhushan Jha, Manish Shukla, Narasimha Kamath and Manoj Kumar Tiwari
Algorithms 2018, 11(4), 54; https://doi.org/10.3390/a11040054 - 20 Apr 2018
Cited by 15 | Viewed by 5224
Abstract
A number of markets, geographically separated, with different demand characteristics for different products that share a common component, are analyzed. This common component can either be manufactured locally in each of the markets or transported between the markets to fulfill the demand. However, [...] Read more.
A number of markets, geographically separated, with different demand characteristics for different products that share a common component, are analyzed. This common component can either be manufactured locally in each of the markets or transported between the markets to fulfill the demand. However, final assemblies are localized to the respective markets. The decision making challenge is whether to manufacture the common component centrally or locally. To formulate the underlying setting, a newsvendor modeling based approach is considered. The developed model is solved using Frank-Wolfe linearization technique along with Benders’ decomposition method. Further, the propensity of decision makers in each market to make suboptimal decisions leading to bounded rationality is considered. The results obtained for both the cases are compared. Full article
(This article belongs to the Special Issue Algorithms for Scheduling Problems)
►▼ Show Figures

Figure 1

13 pages, 652 KiB  
Article
Evaluating Typical Algorithms of Combinatorial Optimization to Solve Continuous-Time Based Scheduling Problem
by Alexander A. Lazarev, Ivan Nekrasov and Nikolay Pravdivets
Algorithms 2018, 11(4), 50; https://doi.org/10.3390/a11040050 - 17 Apr 2018
Cited by 3 | Viewed by 5630
Abstract
We consider one approach to formalize the Resource-Constrained Project Scheduling Problem (RCPSP) in terms of combinatorial optimization theory. The transformation of the original problem into combinatorial setting is based on interpreting each operation as an atomic entity that has a defined duration and [...] Read more.
We consider one approach to formalize the Resource-Constrained Project Scheduling Problem (RCPSP) in terms of combinatorial optimization theory. The transformation of the original problem into combinatorial setting is based on interpreting each operation as an atomic entity that has a defined duration and has to be resided on the continuous time axis meeting additional restrictions. The simplest case of continuous-time scheduling assumes one-to-one correspondence of resources and operations and corresponds to the linear programming problem setting. However, real scheduling problems include many-to-one relations which leads to the additional combinatorial component in the formulation due to operations competition. We research how to apply several typical algorithms to solve the resulted combinatorial optimization problem: enumeration including branch-and-bound method, gradient algorithm, random search technique. Full article
(This article belongs to the Special Issue Algorithms for Scheduling Problems)
►▼ Show Figures

Figure 1

17 pages, 908 KiB  
Article
Near-Optimal Heuristics for Just-In-Time Jobs Maximization in Flow Shop Scheduling
by Helio Yochihiro Fuchigami, Ruhul Sarker and Socorro Rangel
Algorithms 2018, 11(4), 43; https://doi.org/10.3390/a11040043 - 6 Apr 2018
Cited by 8 | Viewed by 5915
Abstract
The number of just-in-time jobs maximization in a permutation flow shop scheduling problem is considered. A mixed integer linear programming model to represent the problem as well as solution approaches based on enumeration and constructive heuristics were proposed and computationally implemented. Instances with [...] Read more.
The number of just-in-time jobs maximization in a permutation flow shop scheduling problem is considered. A mixed integer linear programming model to represent the problem as well as solution approaches based on enumeration and constructive heuristics were proposed and computationally implemented. Instances with up to 10 jobs and five machines are solved by the mathematical model in an acceptable running time (3.3 min on average) while the enumeration method consumes, on average, 1.5 s. The 10 constructive heuristics proposed show they are practical especially for large-scale instances (up to 100 jobs and 20 machines), with very good-quality results and efficient running times. The best two heuristics obtain near-optimal solutions, with only 0.6% and 0.8% average relative deviations. They prove to be better than adaptations of the NEH heuristic (well-known for providing very good solutions for makespan minimization in flow shop) for the considered problem. Full article
(This article belongs to the Special Issue Algorithms for Scheduling Problems)
►▼ Show Figures

Figure 1

15 pages, 320 KiB  
Article
Entropy-Based Algorithm for Supply-Chain Complexity Assessment
by Boris Kriheli and Eugene Levner
Algorithms 2018, 11(4), 35; https://doi.org/10.3390/a11040035 - 24 Mar 2018
Cited by 11 | Viewed by 5120
Abstract
This paper considers a graph model of hierarchical supply chains. The goal is to measure the complexity of links between different components of the chain, for instance, between the principal equipment manufacturer (a root node) and its suppliers (preceding supply nodes). The information [...] Read more.
This paper considers a graph model of hierarchical supply chains. The goal is to measure the complexity of links between different components of the chain, for instance, between the principal equipment manufacturer (a root node) and its suppliers (preceding supply nodes). The information entropy is used to serve as a measure of knowledge about the complexity of shortages and pitfalls in relationship between the supply chain components under uncertainty. The concept of conditional (relative) entropy is introduced which is a generalization of the conventional (non-relative) entropy. An entropy-based algorithm providing efficient assessment of the supply chain complexity as a function of the SC size is developed. Full article
(This article belongs to the Special Issue Algorithms for Scheduling Problems)
►▼ Show Figures

Figure 1

20 pages, 3417 KiB  
Article
A New Greedy Insertion Heuristic Algorithm with a Multi-Stage Filtering Mechanism for Energy-Efficient Single Machine Scheduling Problems
by Hongliang Zhang, Youcai Fang, Ruilin Pan and Chuanming Ge
Algorithms 2018, 11(2), 18; https://doi.org/10.3390/a11020018 - 9 Feb 2018
Cited by 13 | Viewed by 6712
Abstract
To improve energy efficiency and maintain the stability of the power grid, time-of-use (TOU) electricity tariffs have been widely used around the world, which bring both opportunities and challenges to the energy-efficient scheduling problems. Single machine scheduling problems under TOU electricity tariffs are [...] Read more.
To improve energy efficiency and maintain the stability of the power grid, time-of-use (TOU) electricity tariffs have been widely used around the world, which bring both opportunities and challenges to the energy-efficient scheduling problems. Single machine scheduling problems under TOU electricity tariffs are of great significance both in theory and practice. Although methods based on discrete-time or continuous-time models have been put forward for addressing this problem, they are deficient in solution quality or time complexity, especially when dealing with large-size instances. To address large-scale problems more efficiently, a new greedy insertion heuristic algorithm with a multi-stage filtering mechanism including coarse granularity and fine granularity filtering is developed in this paper. Based on the concentration and diffusion strategy, the algorithm can quickly filter out many impossible positions in the coarse granularity filtering stage, and then, each job can find its optimal position in a relatively large space in the fine granularity filtering stage. To show the effectiveness and computational process of the proposed algorithm, a real case study is provided. Furthermore, two sets of contrast experiments are conducted, aiming to demonstrate the good application of the algorithm. The experiments indicate that the small-size instances can be solved within 0.02 s using our algorithm, and the accuracy is further improved. For the large-size instances, the computation speed of our algorithm is improved greatly compared with the classic greedy insertion heuristic algorithm. Full article
(This article belongs to the Special Issue Algorithms for Scheduling Problems)
►▼ Show Figures

Figure 1

Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:
 
Displaying articles 1-12
Back to TopTop