1,720,978 research outputs found
Local search approaches for the test laboratory scheduling problem with variable task grouping
Full text linkThe Test Laboratory Scheduling Problem (TLSP) is a real-world scheduling problem that extends the well-known Resource-Constrained Project Scheduling Problem (RCPSP) by several new constraints. Most importantly, the jobs have to be assembled out of several smaller tasks by the solver, before they can be scheduled. In this paper, we introduce different metaheuristic solution approaches for this problem. We propose four new neighborhoods that modify the grouping of tasks. In combination with neighborhoods for scheduling, they are used by our metaheuristics to produce high-quality solutions for both randomly generated and real-world instances. In particular, Simulated Annealing managed to find solutions that are competitive with the best known results and improve upon the state-of-the-art for larger instances. The algorithm is currently used for the daily planning of a large real-world laboratory
Exact and metaheuristic approaches for unrelated parallel machine scheduling
Full text linkIn this paper, we study an important real-life scheduling problem that can be formulated as an unrelated parallel machine scheduling problem with sequence-dependent setup times, due dates, and machine eligibility constraints. The objective is to minimise total tardiness and makespan. We adapt and extend a mathematical model to find optimal solutions for small instances. Additionally, we propose several variants of simulated annealing to solve very large-scale instances as they appear in practice. We utilise several different search neighbourhoods and additionally investigate the use of innovative heuristic move selection strategies. Further, we provide a set of real-life problem instances as well as a random instance generator that we use to generate a large number of test instances. We perform a thorough evaluation of the proposed techniques and analyse their performance. We also apply our metaheuristics to approach a similar problem from the literature. Experimental results show that our methods are able to improve the results produced with state-of-the-art approaches for a large number of instances
The minimum shift design problem
No full textThe min-SHIFT DESIGN problem (MSD) is an important scheduling problem that
needs to be solved in many industrial contexts. The issue is to find a minimum number of
shifts and the number of employees to be assigned to these shifts in order to minimize the
deviation from workforce requirements.
Our research considers both theoretical and practical aspects of the min-SHIFT DESIGN
problem. This problem is closely related to the minimum edge-cost flow problem (MECF),
a network flow variant that has many applications beyond shift scheduling. We show that
MSD reduces to a special case of MECF and, exploiting this reduction, we prove a logarithmic
hardness of approximation lower bound for MSD. On the basis of these results, we
propose a hybrid heuristic for the problem, which relies on a greedy heuristic followed by a
local search algorithm. The greedy part is based on the network flow analogy, and the local
search algorithm makes use of multiple neighborhood relations
Algorithm selection and instance space analysis for curriculum-based course timetabling
No full textWe propose an algorithm selection approach and an instance space analysis for the well-known curriculum-based course timetabling problem (CB-CTT), which is an important problem for its application in higher education. Several state of the art algorithms exist, including both exact and metaheuristic methods. Results of these algorithms on existing instances in the literature show that there is no single algorithm outperforming the others. Therefore, a deep analysis of the strengths and weaknesses of these algorithms, depending on the instance, is an important research question. In this work, a detailed analysis of the instance space for CB-CTT is performed, charting the regions where these algorithms perform best. We further investigate the application of machine learning methods to automated algorithm selection for CB-CTT, strengthening the insights gained through the instance space analysis. For our research, we contribute new real-life instances and extend the generation of synthetic instances to better correspond to these new instances. Finally, this work shows how instance space analysis and the application of algorithm selection complement each other, underlining the value of both approaches in understanding algorithm performance
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Construct, Merge, Solve and Adapt Applied to a Bus Driver Scheduling Problem with Complex Break Constraints
No full textBus Driver Scheduling (BDS) is a combinatorial optimization problem that consists in assigning atomic driving duties (legs) belonging to predetermined routes to bus drivers. We consider the highly-constrained, real-world version of the problem proposed by Kletzander and Musliu (2020), with complex break rules specified by a collective agreement and public regulation. We propose a Construct, Merge, Solve and Adapt (CMSA) algorithm, which is a recent metaheuristic proposed by Blum et al. (2016) based on the idea of problem instance reduction. At each iteration of the algorithm, sub-instances of the original instance are solved by an exact solver. These sub-instances are obtained by merging the components of the solutions generated by a probabilistic greedy algorithm. We compare our method with the state-of-the-art approaches on the benchmark instances. The results show that CMSA compares favourably with other metaheuristics on most instances and with exact techniques on large ones
Local search for shift design
No full textDesigning shifts is one of the important stages in the general workforce scheduling process. In this paper we consider solving the shift design problem by using local search methods. First we propose a set of move types that give rise to a composite neighbourhood relation. In the move selection process, we make use of the basic prohibition mechanisms of tabu search. In addition, in order to avoid having to explore the whole neighbourhood which could be prohibitively large, we evaluate the moves in decreasing order of their promise to yield some improvement. Furthermore, we propose an algorithm for generating a good initial solution, which also exploits knowledge about requirements and shift structure. Experimental results on both real-life and randomly-generated instances show the advantages of these ingredients. The solver is part of a commercial product and has shown to work well in practical cases
- …
