Research

26 pages, 3091 KiB

Open AccessArticle

Non-Sequential Linear Construction Project Scheduling Model for Minimizing Idle Equipment Using Constraint Programming (CP)

by Shu-Shun Liu, Agung Budiwirawan and Muhammad Faizal Ardhiansyah Arifin

Mathematics 2021, 9(19), 2492; https://0-doi-org.brum.beds.ac.uk/10.3390/math9192492 - 05 Oct 2021

Cited by 1 | Viewed by 1791

Abstract

Over the last several decades, the scheduling of linear construction projects (LCPs) has been explored extensively by experts. The linear scheduling method (LSM), which focuses on work rate and work continuity, has the advantage of tackling LCPs’ scheduling problems. The traditional LSM uses [...] Read more.

Over the last several decades, the scheduling of linear construction projects (LCPs) has been explored extensively by experts. The linear scheduling method (LSM), which focuses on work rate and work continuity, has the advantage of tackling LCPs’ scheduling problems. The traditional LSM uses work continuity to monitor resource allocation continuity on the premise that activities with the same type of work use the same crew. However, some LCPs require a combination of different types of equipment to comprise the crew. Sometimes, parts of different crews require the same types of equipment, and sometimes, the same crew requires different equipment configurations. This causes the pattern of work continuity to be different from the pattern of resource allocation continuity. Therefore, we propose an optimization model of the LSM to minimize idle equipment on a non-sequential linear construction project—i.e., a road network maintenance project. This model is intended to minimize the number of idle equipment and their idle time to achieve more efficient scheduling for linear construction projects. This model offers novel details of resource allocation continuity assessment by taking into account equipment combination and configuration (ECC). Therefore, the scheduling concept used by the proposed model is named the linear scheduling model with ECC (LSM–ECC). The model was developed using constraint programming (CP), as CP has good performance and robustness in the optimization field. The model was implemented to a representation of a road network maintenance project and has satisfactory results. Full article

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

► Show Figures

Figure 1

22 pages, 1839 KiB

Open AccessArticle

An Imitation and Heuristic Method for Scheduling with Subcontracted Resources

by Anna Antonova, Konstantin Aksyonov and Olga Aksyonova

Mathematics 2021, 9(17), 2098; https://0-doi-org.brum.beds.ac.uk/10.3390/math9172098 - 30 Aug 2021

Cited by 2 | Viewed by 1486

Abstract

A scheduling problem with subcontracted resources is widely spread and is associated with the distribution of limited renewable and non-renewable resources, both own and subcontracted ones based on the work’s due dates and the earliest start time. Scheduling’s goal is to reduce the [...] Read more.

A scheduling problem with subcontracted resources is widely spread and is associated with the distribution of limited renewable and non-renewable resources, both own and subcontracted ones based on the work’s due dates and the earliest start time. Scheduling’s goal is to reduce the cost of the subcontracted resources. In the paper, application of a few scheduling methods based on scheduling theory and the optimization algorithm is considered; limitations of these methods’ application are highlighted. It is shown that the use of simulation modeling with heuristic rules for allocation of the renewable resources makes it possible to overcome the identified limitations. A new imitation and heuristic method for solving the assigned scheduling problem is proposed. The comparison of the new method with existing ones in terms of the quality of the found solution and performance of the methods is carried out. A case study is presented that allowed a four-fold reduction of the overall subcontracted resources cost in a real project portfolio. Full article

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

► Show Figures

Figure 1

35 pages, 446 KiB

Open AccessArticle

Relocation Scheduling in a Two-Machine Flow Shop with Resource Recycling Operations

by Ting-Chun Lo and Bertrand M. T. Lin

Mathematics 2021, 9(13), 1527; https://0-doi-org.brum.beds.ac.uk/10.3390/math9131527 - 29 Jun 2021

Cited by 2 | Viewed by 1417

Abstract

This paper considers a variant of the relocation problem, which is formulated from an urban renewal project. There is a set of jobs to be processed in a two-machine flow shop subject to a given initial resource level. Each job consumes some units [...] Read more.

This paper considers a variant of the relocation problem, which is formulated from an urban renewal project. There is a set of jobs to be processed in a two-machine flow shop subject to a given initial resource level. Each job consumes some units of the resource to start its processing on machine 1 and will return some amount of the resource when it is completed on machine 2. The amount of resource released by a job is not necessarily equal to the amount of resource acquired by the job for starting the process. Subject to the resource constraint, the problem is to find a feasible schedule whose makespan is minimum. In this paper, we first prove the NP-hardness of two special cases. Two heuristic algorithms with different processing characteristics, permutation and non-permutation, are designed to construct feasible schedules. Ant colony optimization (ACO) algorithms are also proposed to produce approximate solutions. We design and conduct computational experiments to appraise the performances of the proposed algorithms. Full article

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

► Show Figures

Figure 1

22 pages, 984 KiB

Open AccessArticle

A Kronecker Algebra Formulation for Markov Activity Networks with Phase-Type Distributions

by Alessio Angius, András Horváth and Marcello Urgo

Mathematics 2021, 9(12), 1404; https://0-doi-org.brum.beds.ac.uk/10.3390/math9121404 - 17 Jun 2021

Cited by 5 | Viewed by 1789

Abstract

The application of theoretical scheduling approaches to the real world quite often crashes into the need to cope with uncertain events and incomplete information. Stochastic scheduling approaches exploiting Markov models have been proposed for this class of problems with the limitation to exponential [...] Read more.

The application of theoretical scheduling approaches to the real world quite often crashes into the need to cope with uncertain events and incomplete information. Stochastic scheduling approaches exploiting Markov models have been proposed for this class of problems with the limitation to exponential durations. Phase-type approximations provide a tool to overcome this limitation. This paper proposes a general approach for using phase-type distributions to model the execution of a network of activities with generally distributed durations through a Markov chain. An analytical representation of the infinitesimal generator of the Markov chain in terms of Kronecker algebra is proposed, providing a general formulation for this class of problems and supporting more efficient computation methods. This entails the capability to address stochastic scheduling in terms of the estimation of the distribution of common objective functions (i.e., makespan, lateness), enabling the use of risk measures to address robustness. Full article

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

► Show Figures

Figure 1

15 pages, 1297 KiB

Open AccessArticle

Improving the Return Loading Rate Problem in Northwest China Based on the Theory of Constraints

by Wen-Tso Huang, Cheng-Chang Lu and Jr-Fong Dang

Mathematics 2021, 9(12), 1397; https://0-doi-org.brum.beds.ac.uk/10.3390/math9121397 - 16 Jun 2021

Cited by 1 | Viewed by 1270

Abstract

This paper introduces how to improve the return loading rate problem by integrating the Sub-Tour reversal approach with the method of the Theory of Constraints (TOC). The proposed model generates the initial solution derived by the Sub-Tour reversal approach in phase 1 and [...] Read more.

This paper introduces how to improve the return loading rate problem by integrating the Sub-Tour reversal approach with the method of the Theory of Constraints (TOC). The proposed model generates the initial solution derived by the Sub-Tour reversal approach in phase 1 and then applies TOC to obtain the optimal solution, meeting the goal of improving the return loading rate to more than 50% and then lowering the total transportation distance in phase 2. To see our model capability, this study establishes an original distribution layout to compare the performance of the Sub-Tour reversal approach with our model, based on the simulation data generated by the Monte Carlo simulation. We also conduct the pair t-test to verify our model performance. The results show that our proposed model outperforms the Sub-Tour reversal approach in a significant manner. By utilizing the available data, our model can be easily implemented in the real world and efficiently seeks the optimal solutions. Full article

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

► Show Figures

Figure 1

18 pages, 2013 KiB

Open AccessArticle

No-Idle Flowshop Scheduling for Energy-Efficient Production: An Improved Optimization Framework

by Chen-Yang Cheng, Shih-Wei Lin, Pourya Pourhejazy, Kuo-Ching Ying and Yu-Zhe Lin

Mathematics 2021, 9(12), 1335; https://0-doi-org.brum.beds.ac.uk/10.3390/math9121335 - 09 Jun 2021

Cited by 6 | Viewed by 2269

Abstract

Production environment in modern industries, like integrated circuits manufacturing, fiberglass processing, steelmaking, and ceramic frit, is characterized by zero idle-time between inbound and outbound jobs on every machine; this technical requirement improves energy efficiency, hence, has implications for cleaner production in other production [...] Read more.

Production environment in modern industries, like integrated circuits manufacturing, fiberglass processing, steelmaking, and ceramic frit, is characterized by zero idle-time between inbound and outbound jobs on every machine; this technical requirement improves energy efficiency, hence, has implications for cleaner production in other production situations. An exhaustive review of literature is first conducted to shed light on the development of no-idle flowshops. Considering the intractable nature of the problem, this research also develops an extended solution method for optimizing the Bi-objective No-Idle Permutation Flowshop Scheduling Problem (BNIPFSP). Extensive numerical tests and statistical analysis are conducted to evaluate the developed method, comparing it with the best-performing algorithm developed to solve the BNIPFSP. Overall, the proposed extension outperforms in terms of solution quality at the expense of a longer computational time. This research is concluded by providing suggestions for the future development of this understudied scheduling extension. Full article

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

► Show Figures

Figure 1

20 pages, 2066 KiB

Open AccessArticle

A Hybrid Metaheuristic for the Unrelated Parallel Machine Scheduling Problem

by Dung-Ying Lin and Tzu-Yun Huang

Mathematics 2021, 9(7), 768; https://0-doi-org.brum.beds.ac.uk/10.3390/math9070768 - 01 Apr 2021

Cited by 8 | Viewed by 2686

Abstract

The unrelated parallel machine scheduling problem aims to assign jobs to independent machines with sequence-dependent setup times so that the makespan is minimized. When many practical considerations are introduced, solving the resulting problem is challenging, especially when problems of realistic sizes are of [...] Read more.

The unrelated parallel machine scheduling problem aims to assign jobs to independent machines with sequence-dependent setup times so that the makespan is minimized. When many practical considerations are introduced, solving the resulting problem is challenging, especially when problems of realistic sizes are of interest. In this study, in addition to the conventional objective of minimizing the makespan, we further consider the burn-in (B/I) procedure that is required in practice; we need to ensure that the scheduling results satisfy the B/I ratio constrained by the equipment. To solve the resulting complicated problem, we propose a population-based simulated annealing algorithm embedded with a variable neighborhood descent technique. Empirical results show that the proposed solution strategy outperforms a commonly used commercial optimization package; it can obtain schedules that are better than the schedules used in practice, and it does so in a more efficient manner. Full article

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

► Show Figures

Figure 1

17 pages, 311 KiB

Open AccessArticle

Two-Agent Pareto-Scheduling of Minimizing Total Weighted Completion Time and Total Weighted Late Work

by Yuan Zhang, Zhichao Geng and Jinjiang Yuan

Mathematics 2020, 8(11), 2070; https://0-doi-org.brum.beds.ac.uk/10.3390/math8112070 - 20 Nov 2020

Cited by 13 | Viewed by 1577

Abstract

We investigate the Pareto-scheduling problem with two competing agents on a single machine to minimize the total weighted completion time of agent A’s jobs and the total weighted late work of agent B’s jobs, the B-jobs having a common due [...] Read more.

We investigate the Pareto-scheduling problem with two competing agents on a single machine to minimize the total weighted completion time of agent A’s jobs and the total weighted late work of agent B’s jobs, the B-jobs having a common due date. Since this problem is known to be NP-hard, we present two pseudo-polynomial-time exact algorithms to generate the Pareto frontier and an approximation algorithm to generate a

(1 + ϵ)

-approximate Pareto frontier. In addition, some numerical tests are undertaken to evaluate the effectiveness of our algorithms. Full article

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

► Show Figures

Figure 1

18 pages, 12015 KiB

Open AccessArticle

Two-Agent Preemptive Pareto-Scheduling to Minimize Late Work and Other Criteria

by Ruyan He and Jinjiang Yuan

Mathematics 2020, 8(9), 1517; https://0-doi-org.brum.beds.ac.uk/10.3390/math8091517 - 05 Sep 2020

Cited by 9 | Viewed by 1619

Abstract

In this paper, we consider three preemptive Pareto-scheduling problems with two competing agents on a single machine. In each problem, the objective function of agent A is the total completion time, the maximum lateness, or the total late work while the objective function [...] Read more.

In this paper, we consider three preemptive Pareto-scheduling problems with two competing agents on a single machine. In each problem, the objective function of agent A is the total completion time, the maximum lateness, or the total late work while the objective function of agent B is the total late work. For each problem, we provide a polynomial-time algorithm to characterize the trade-off curve of all Pareto-optimal points. Full article

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

► Show Figures

Figure 1

Journal Menu

Journal Browser

Theoretical and Computational Research in Various Scheduling Models

Share This Special Issue

Special Issue Editors

Special Issue Information

Keywords

Published Papers (9 papers)

Research

Further Information

Guidelines

MDPI Initiatives

Follow MDPI