Mathematics

Research

19 pages, 3060 KiB

Open AccessArticle

Pareto Optimization of Energy-Saving Timetables Considering the Non-Parallel Operation of Multiple Trains on a Metro Line

by Weiya Chen, Jiaqi Lu, Hengpeng Zhang and Ziyue Yuan

Mathematics 2023, 11(21), 4491; https://doi.org/10.3390/math11214491 - 30 Oct 2023

Cited by 1 | Viewed by 1439

Abstract

In light of reducing train operation energy consumption while maintaining the passenger service level for creating sustainable urban rail transit systems, we address a non-parallel train timetabling problem considering regenerative braking energy utilization and the non-parallel operation of multiple trains on a metro [...] Read more.

In light of reducing train operation energy consumption while maintaining the passenger service level for creating sustainable urban rail transit systems, we address a non-parallel train timetabling problem considering regenerative braking energy utilization and the non-parallel operation of multiple trains on a metro line via a newly proposed multi-objective timetable (MOT) optimization model and an evolutionary algorithm based on NSGA-II. The optimization objectives of the MOT model are to find satisfactory energy-saving timetables on the Pareto frontier by minimizing the total travel time of passengers and minimizing the net energy consumption of trains. An improved multi-objective evolutionary algorithm based on NSGA-II is constructed to generate the optimal arrival and departure times at each station for each train running in a non-parallel operation mode. This study tests the feasibility of the proposed optimization method via an empirical case using the data collected from the Yizhuang Line of the Beijing metro systems in China. The simulation results show that the proposed optimization method satisfies both the energy utilization and passenger service levels along a Pareto front. The MOT improves the overall effectiveness of regenerative braking energy utilization by 29.88% in comparison with the original timetable; it reduces the net operation energy consumption by 44.86% relative to the travel-oriented timetable (TOT); and it reduces the total passenger travel time by 27.18% compared with the energy-oriented timetable (EOT). Full article

(This article belongs to the Special Issue Theoretical and Computational Research in Various Scheduling Models, 2nd Edition)

► Show Figures

Figure 1

37 pages, 1716 KiB

Open AccessArticle

Optimum Scheduling of a Multi-Machine Flexible Manufacturing System Considering Job and Tool Transfer Times without Tool Delay

by Sunil Prayagi, Padma Lalitha Mareddy, Lakshmi Narasimhamu Katta and Sivarami Reddy Narapureddy

Mathematics 2023, 11(19), 4190; https://doi.org/10.3390/math11194190 - 7 Oct 2023

Viewed by 1329

Abstract

In order to minimize makespan (C_max) without causing tool delay with the fewest copies of each tool type, this study investigates the concurrent scheduling of automated guided vehicles (AGVs), machines (MCs), tool transporter (TT), and tools in a multi-machine flexible manufacturing [...] Read more.

In order to minimize makespan (C_max) without causing tool delay with the fewest copies of each tool type, this study investigates the concurrent scheduling of automated guided vehicles (AGVs), machines (MCs), tool transporter (TT), and tools in a multi-machine flexible manufacturing system (FMS). The tools are housed in a central tool magazine (CTM), accessible to and utilized by several machines. AGVs and the tool transporter (TT) move jobs and tools between machines. Since it involves allocating tool copies and AGVs to job operations, sequencing job operations on machines, and related trip operations, such as AGVs’ and TT’s empty trip and loaded trip times, this simultaneous scheduling problem is highly complicated. This issue is resolved using the symbiotic organisms search algorithm (SOSA), based on the symbiotic interaction strategies that organisms adapt to survive in the ecosystem. This study proposes a mixed nonlinear integer programming formulation to address this problem. Verification is performed using an industrial problem from a manufacturing organization. The results show that employing two copies for two tool types out of 22 tool kinds and one copy for the remaining tool types results in no tool delay, which causes a reduction in the C_max as well as cost. The industries that can benefit directly from this study are consumer electronics manufacturers, original equipment manufacturers, automobile manufacturers, and textile machine producers. The results demonstrate that the SOSA provides promising results compared to the flower pollination algorithm (FPA). Full article

(This article belongs to the Special Issue Theoretical and Computational Research in Various Scheduling Models, 2nd Edition)

► Show Figures

Figure 1

15 pages, 395 KiB

Open AccessArticle

Balancing the Average Weighted Completion Times in Large-Scale Two-Agent Scheduling Problems: An Evolutionary-Type Computational Study

by Matteo Avolio

Mathematics 2023, 11(19), 4034; https://doi.org/10.3390/math11194034 - 22 Sep 2023

Cited by 1 | Viewed by 834

Abstract

The problem of balancing the average weighted completion times of two classes of jobs is an NP-hard scheduling problem that was very recently introduced in the literature. Interpreted as a cooperative-type two-agent single-machine problem, its applications are in various practical contexts such as [...] Read more.

The problem of balancing the average weighted completion times of two classes of jobs is an NP-hard scheduling problem that was very recently introduced in the literature. Interpreted as a cooperative-type two-agent single-machine problem, its applications are in various practical contexts such as in logistics for balancing the delivery times, in manufacturing for balancing the assembly lines and in services for balancing the waiting times of groups of people. The only solution technique currently existing in the literature is a Lagrangian heuristic, based on solving a finite number of successive linear assignment problems, whose dimension depends on the total number of jobs. Since the Lagrangian approach has not appeared to be particularly suitable for solving large-scale problems, to overcome this drawback, we propose to face the problem by means of a genetic algorithm. Differently from the Lagrangian heuristic, our approach is found to be effective also for large instances (up to 2000 jobs), as confirmed by numerical experiments. Full article

(This article belongs to the Special Issue Theoretical and Computational Research in Various Scheduling Models, 2nd Edition)

► Show Figures

Figure 1

14 pages, 518 KiB

Open AccessArticle

Contention-Free Scheduling for Single Preemption Multiprocessor Platforms

by Hyeongboo Baek and Jaewoo Lee

Mathematics 2023, 11(16), 3547; https://doi.org/10.3390/math11163547 - 16 Aug 2023

Cited by 1 | Viewed by 1137

Abstract

The Contention-Free (CF) policy has been extensively researched in the realm of real-time multi-processor scheduling due to its wide applicability and the performance enhancement benefits it provides to existing scheduling algorithms. The CF policy improves the feasibility of executing other real-time tasks by [...] Read more.

The Contention-Free (CF) policy has been extensively researched in the realm of real-time multi-processor scheduling due to its wide applicability and the performance enhancement benefits it provides to existing scheduling algorithms. The CF policy improves the feasibility of executing other real-time tasks by assigning the lowest priority to a task at a moment when it is guaranteed not to miss its deadline during the remaining execution time. Despite its effectiveness, existing studies on the CF policy are largely confined to preemptive scheduling, leaving the efficiency and applicability of limited preemption scheduling unexplored. Limited preemption scheduling permits a job to execute to completion with a limited number of preemptions, setting it apart from preemptive scheduling. This type of scheduling is crucial when preemption or migration overheads are either excessively large or unpredictable. In this paper, we introduce SP-CF, a single preemption scheduling approach that incorporates the CF policy. SP-CF allows a preemption only once during each job’s execution, following a priority demotion under the CF policy. We also propose a new schedulability analysis method for SP-CF to determine whether each task is executed in a timely manner and without missing its deadline. Through simulation experiments, we demonstrate that SP-CF can significantly enhance the schedulability of the traditional rate-monotonic algorithm and the earliest deadline first algorithm. Full article

(This article belongs to the Special Issue Theoretical and Computational Research in Various Scheduling Models, 2nd Edition)

► Show Figures

Figure 1

22 pages, 573 KiB

Open AccessArticle

Lagrangian Heuristic for Multi-Depot Technician Planning of Product Distribution and Installation with a Lunch Break

by Fangzhou Yan, Huaxin Qiu and Dongya Han

Mathematics 2023, 11(3), 510; https://doi.org/10.3390/math11030510 - 18 Jan 2023

Viewed by 1439

Abstract

In this paper, we consider a technician planning scheme stemming from product distribution and installation in a manufacturing enterprise that considers factors such as soft time windows, skill areas, lunch breaks, and outsourcing options, among others. The goal is to identify the optimal [...] Read more.

In this paper, we consider a technician planning scheme stemming from product distribution and installation in a manufacturing enterprise that considers factors such as soft time windows, skill areas, lunch breaks, and outsourcing options, among others. The goal is to identify the optimal partition of technicians into groups and assignment of customers to technician groups and find the optimal routes for technician groups to minimize the sum of the travel cost, soft time window violation cost, and outsourcing cost. To address this problem, the study develops a tailored Lagrangian heuristic that incorporates several strategies to speed up convergence and produce sharper bounds. Computational comparisons between the developed heuristic and MIP solver are presented. The results reveal that the bounds found by the developed algorithm outperform those found by CPLEX for large instances, and it is capable of identifying high-quality feasible solutions to large-scale problems. Full article

(This article belongs to the Special Issue Theoretical and Computational Research in Various Scheduling Models, 2nd Edition)

► Show Figures

Figure 1

20 pages, 2486 KiB

Open AccessArticle

Equilibrium Optimizer and Slime Mould Algorithm with Variable Neighborhood Search for Job Shop Scheduling Problem

by Yuanfei Wei, Zalinda Othman, Kauthar Mohd Daud, Shihong Yin, Qifang Luo and Yongquan Zhou

Mathematics 2022, 10(21), 4063; https://doi.org/10.3390/math10214063 - 1 Nov 2022

Cited by 10 | Viewed by 2101

Abstract

Job Shop Scheduling Problem (JSSP) is a well-known NP-hard combinatorial optimization problem. In recent years, many scholars have proposed various metaheuristic algorithms to solve JSSP, playing an important role in solving small-scale JSSP. However, when the size of the problem increases, the algorithms [...] Read more.

Job Shop Scheduling Problem (JSSP) is a well-known NP-hard combinatorial optimization problem. In recent years, many scholars have proposed various metaheuristic algorithms to solve JSSP, playing an important role in solving small-scale JSSP. However, when the size of the problem increases, the algorithms usually take too much time to converge. In this paper, we propose a hybrid algorithm, namely EOSMA, which mixes the update strategy of Equilibrium Optimizer (EO) into Slime Mould Algorithm (SMA), adding Centroid Opposition-based Computation (COBC) in some iterations. The hybridization of EO with SMA makes a better balance between exploration and exploitation. The addition of COBC strengthens the exploration and exploitation, increases the diversity of the population, improves the convergence speed and convergence accuracy, and avoids falling into local optimum. In order to solve discrete problems efficiently, a Sort-Order-Index (SOI)-based coding method is proposed. In order to solve JSSP more efficiently, a neighbor search strategy based on a two-point exchange is added to the iterative process of EOSMA to improve the exploitation capability of EOSMA to solve JSSP. Then, it is utilized to solve 82 JSSP benchmark instances; its performance is evaluated compared to that of EO, Marine Predators Algorithm (MPA), Aquila Optimizer (AO), Bald Eagle Search (BES), and SMA. The experimental results and statistical analysis show that the proposed EOSMA outperforms other competing algorithms. Full article

(This article belongs to the Special Issue Theoretical and Computational Research in Various Scheduling Models, 2nd Edition)

► Show Figures

Figure 1

17 pages, 2607 KiB

Open AccessArticle

Application of an Adaptive Adjacency Matrix-Based Graph Convolutional Neural Network in Taxi Demand Forecasting

by Jian-You Xu, Shuo Zhang, Chin-Chia Wu, Win-Chin Lin and Qing-Li Yuan

Mathematics 2022, 10(19), 3694; https://doi.org/10.3390/math10193694 - 9 Oct 2022

Cited by 4 | Viewed by 2354

Abstract

Accurate forecasting of taxi demand has facilitated the rational allocation of urban public transport resources, reduced congestion in urban transport networks, and shortened passenger waiting time. However, virtual station discovery and modelling of the demand when forecasting through graph convolutional neural networks remains [...] Read more.

Accurate forecasting of taxi demand has facilitated the rational allocation of urban public transport resources, reduced congestion in urban transport networks, and shortened passenger waiting time. However, virtual station discovery and modelling of the demand when forecasting through graph convolutional neural networks remains challenging. In this study, the virtual station discovery problem was addressed by using a two-stage clustering approach, which considers the geographical and load characteristics of taxi demand. Furthermore, a fusion model combining non-negative matrix decomposition and a graph convolutional neural network was proposed in order to extract the features of the nodes for dimension reduction and adaptive adjacency matrix computation. By the construction of a local processing structure, further extraction of the local characteristics of the demand was achieved. The experimental results show that the method in this study outperforms state-of-the-art methods in terms of the root mean square error and average absolute value error. Therefore, the model proposed in this study is able to achieve accurate forecasting of taxi demand. Full article

(This article belongs to the Special Issue Theoretical and Computational Research in Various Scheduling Models, 2nd Edition)

► Show Figures

Figure 1

17 pages, 6801 KiB

Open AccessArticle

Robust Scheduling of Two-Agent Customer Orders with Scenario-Dependent Component Processing Times and Release Dates

by Chin-Chia Wu, Jatinder N. D. Gupta, Win-Chin Lin, Shuenn-Ren Cheng, Yen-Lin Chiu, Juin-Han Chen and Long-Yuan Lee

Mathematics 2022, 10(9), 1545; https://doi.org/10.3390/math10091545 - 4 May 2022

Cited by 4 | Viewed by 1619

Abstract

Although some uncertainty factors can occur in many practical environments, customer order scheduling problems involving two agents in such uncertain environments have not received attention in the current literature. Motivated by this observation, we address a two-agent customer order scheduling problem where various [...] Read more.

Although some uncertainty factors can occur in many practical environments, customer order scheduling problems involving two agents in such uncertain environments have not received attention in the current literature. Motivated by this observation, we address a two-agent customer order scheduling problem where various customer orders have scenario-dependent component processing times and release dates in order to find an appropriate schedule to minimize the maximum of the total completion time of the customer orders that belong to one agent and are subject to a constraint with the other agent. In order to solve this problem, a lower bound and six dominant properties are derived and used to propose a branch-and-bound algorithm to find an exact optimal solution. Afterward, three local search heuristics and two variants of a simulated annealing hyper-heuristic are proposed and empirically evaluated in order to find approximate solutions. Finally, we conclude the paper with a summary of our findings and some directions for future research. Full article

(This article belongs to the Special Issue Theoretical and Computational Research in Various Scheduling Models, 2nd Edition)

► Show Figures

Figure 1

Journal Menu

Journal Browser

Theoretical and Computational Research in Various Scheduling Models, 2nd Edition

Share This Special Issue

Special Issue Editors

Special Issue Information

Keywords

Benefits of Publishing in a Special Issue

Published Papers (8 papers)

Research

Further Information

Guidelines

MDPI Initiatives

Follow MDPI