Search

The generation maintenance scheduling deals with a time sequence of preventive maintenance outages for a given set of generation units in an electricity market subject to power system restrictions. Incorporating a leader–follower structure in generation maintenance scheduling models is essential because of the inherent conflict between the interests of an independent system operator (ISO) and generation companies (GENCOs). The present paper proposes a new preventive maintenance scheduling model for generation companies facing the risk of involving generation units' disruption and demand variations while ensuring the reliability of the power system. Each GENCO proposes the maintenance schedule of its generation units to the ISO in a non-cooperative manner intending to maximize its net profit. Then ISO reacts to the aggregated schedule according to the power system's reliability index. Thus, a new formula is developed to consider all the interactions between the power system's stakeholders. In this regard, a stochastic multi-leader one-follower approach is applied. The GENCOs are considered independent leaders at the upper-level and the ISO is considered a follower at the lower-level. Then an equivalent single-level counterpart model is presented for each leader. So, the whole problem is converted into multiple individual stochastic single-level models, and then the Nash Equilibrium concept is used to determine GENCO equilibrium strategies. The proposed methodology is evaluated using some modified IEEE reliability test systems. The numerical analysis confirms that the proposed model is more effective in cases with higher uncertainties. Moreover, the performed analysis demonstrated the importance of applying a bi-level approach to the problem. Finally, the superiority of the proposed approach compared to the existing one is confirmed. [ABSTRACT FROM AUTHOR]

We investigate the seemingly untouched yet the most general parallel identical k-stage flow-shops scheduling, in which we are given an arbitrary number of indistinguishable k-stage flow-shops and a set of jobs each to be processed on one of the flow-shops, and the goal is to schedule these jobs to the flow-shops so as to minimize the makespan. Here the number k of stages is a fixed constant, but the number of flow-shops is part of the input. This scheduling problem is strongly NP-hard. To the best of our knowledge all previously presented approximation algorithms are for the special case where k = 2 , including a 17/6-approximation in 2017, a (2 + ϵ) -approximation in 2018, and the most recent polynomial-time approximation scheme in 2020; they all take advantage of the number of stages being two. We deal with an arbitrary constant k ≥ 3 , where the k-stage flow-shop scheduling is already strongly NP-hard. To define a configuration that summarizes the key information about the job assignments in a feasible schedule, we present novel concepts of big job type, big job assignment pair type, and flow-shop type. We show that the total number of distinct configurations is a polynomial in the input number of flow-shops. We then present how to compute a schedule for each configuration that assigns all the big jobs, followed by how to allocate all the small jobs into the schedule at a cost only a fraction of the makespan. These together lead to a polynomial-time approximation scheme for the problem. [ABSTRACT FROM AUTHOR]

This paper considers several two-machine open shop problems with two agents. Each agent has an independent set of nonpreemptive jobs, and the objective is to find either a schedule minimizing a linear combination of the makespans of both agents, a schedule minimizing the makespan of one agent with the makespan of the other agent not exceeding a threshold, or all Pareto-optimal schedules with respect to the makespans of both agents. We present a number of results for the problems above, including a polynomial algorithm and a pseudo-polynomial algorithm for special cases, non-approximability, two approximation algorithms, and a fully polynomial-time approximation scheme. Finally, we run numerical experiments to show the effectiveness of the pseudo-polynomial algorithm and the approximation algorithms. [ABSTRACT FROM AUTHOR]

This paper introduces the d-distanceb-matching problem, in which we are given a bipartite graph G = (S , T ; E) with S = { s 1 , ⋯ , s n } , a weight function on the edges, an integer d ∈ Z + and a degree bound function b : S ∪ T → Z + . The goal is to find a maximum-weight subset M ⊆ E of the edges satisfying the following two conditions: (1) the degree of each node v ∈ S ∪ T is at most b(v) in M, (2) if s i t , s j t ∈ M , then | i - j | ≥ d . In the cyclic version of the problem, the nodes in S are considered to be in cyclic order. We get back the (cyclic)d-distance matching problem when b (s) = 1 for s ∈ S and b (t) = ∞ for t ∈ T . We prove that the d-distance matching problem is APX-hard, even in the unweighted case. We show that 2 - 1 d is a tight upper bound on the integrality gap of the natural integer programming model for the cyclic d-distance b-matching problem provided that (2 d - 1) divides the size of S. For the non-cyclic case, the integrality gap is shown to be at most (2 - 2 d) . The proofs give approximation algorithms with guarantees matching these bounds, and also improve the best known algorithms for the (cyclic) d-distance matching problem. In a related problem, our goal is to find a permutation of S maximizing the weight of the optimal d-distance b-matching. This problem can be solved in polynomial time for the (cyclic) d-distance matching problem — even though the (cyclic) d-distance matching problem itself is NP-hard and also hard to approximate arbitrarily. For (cyclic) d-distance b-matchings, however, we prove that finding the best permutation is NP-hard, even if b ≡ 2 or d = 2 , and we give e-approximation algorithms. [ABSTRACT FROM AUTHOR]

A container terminal plays a significant role in global supply chain. Coordinated scheduling is one of the most important issues for sustainable development of container terminals. This research provides an in-depth survey of the coordinated scheduling for container terminals in order to identify existing research streams for future investigations. Researches on the coordinated scheduling of container terminals which are published between 2010 and 2021 are reviewed and classified. Related coordinated scheduling models and solution methods are analyzed. Research gaps and future directions are also lighted up. This will help new researchers quickly understanding the distribution of researches on these fields. The findings are important for both research and practice perspectives. [ABSTRACT FROM AUTHOR]

After a natural disaster or a large-scale incident, some of the utility lines and essential roads around the damaged centers may be blocked by debris from the disaster. This incident can immediately restrict crucial supply distribution and affect rescue plans. Therefore, the recovery of damaged roads is an essential step to help increase the effectiveness of the relief operations and to reduce victims' suffering. In this study, we develop a mixed-integer programming model for optimal scheduling and routing of repair crew and relief vehicles after the disaster. The objective function is to minimize the total relief time of the disaster-affected nodes and the recovery time of damaged nodes. Demand nodes are manually weighed according to a presumed degree of damage. Given the NP-hardness nature of the problem, a hybrid approach is proposed based on the Benders decomposition method and a heuristic algorithm. The heuristic algorithm is employed as an initiation algorithm to generate an initial solution for the Benders decomposition algorithm. The routing of the repair crew and relief vehicles is drawn using the Benders decomposition algorithm. To demonstrate the performance of the hybrid algorithm, an ant colony optimization algorithm is also developed. The computational results demonstrate that the proposed approach is capable of computing a near-optimal solution in less CPU time. Furthermore, the performance of this hybrid approach is distinctively superior when it comes to routing of medium to large-scale problems. [ABSTRACT FROM AUTHOR]

In this paper we consider the coupled task scheduling problem with exact delay times on a single machine with the objective of minimizing the total completion time of the jobs. We provide constant-factor approximation algorithms for several variants of this problem that are known to be N P -hard, while also proving N P -hardness for two variants whose complexity was unknown before. Using these results, together with constant-factor approximations for the makespan objective from the literature, we also introduce the first results on bi-objective approximation in the coupled task setting. [ABSTRACT FROM AUTHOR]

This paper studies a two-machine flow shop scheduling problem with availability constraints due to a breakdown on the first machine. The starting time of the breakdown is considered stochastic and follows a known probability distribution. A service-level constraint is introduced to model the guarantee with which the obtained schedule takes into account the stochastic nature of the breakdown's starting time. The objective is to find a solution that minimizes the makespan while satisfying the desired service level. The studied problem is strongly NP-hard. We develop two mixed integer linear models that linearize the non-linear model. Using interval modeling of the breakdown, we propose lower bounds and a valid inequality that are used to strengthen both models. When the lower bounds and the valid inequality are applied, the performance of both models is greatly improved by reducing the gap and reaching optimality for more instances. We also introduced two heuristics that exploit the proposed interval modeling. The computational results indicate that both models are able to reach optimality for the 10-job instances. Moreover, the comparisons results between both models with the two heuristics showed their effectiveness. [ABSTRACT FROM AUTHOR]

Suppose identical jobs need to be processed by a single processor. Processing is carried out one job after the other, in batches, and jobs are released only when their entire batch is done. Each job is held by an agent, who tries to minimize costs. The cost of an individual job is linear in two terms: a congestion cost, dependent on the size of the batch, and a lateness cost, dependent also on the number of jobs preceding the batch. The agents need to decide on the sequential index of the batch they ascribe to. This decision problem is stated as a non-cooperative game, with applications both in ride sharing and in queues in which the server must never be idle. We derive its (mixed) symmetric equilibrium, which always exists, and its pure non-symmetric equilibrium, when it exists. The corresponding social optimization problem is solved as well, leading, in the mixed symmetric case, to an explicit formula for the price of anarchy. [ABSTRACT FROM AUTHOR]

This paper provides two new perspectives on single-machine scheduling problems in which the objective involves penalties regarding late work. Both of this perspectives have been neglected in the previous literature. We begin by presenting a parameterized complexity analysis of the N P -hard problem of minimizing the total late work on a single machine. We do so with respect to the following four parameters: (i) the number of different processing times ( υ p ); (ii) the number of different due dates ( υ d ); (iii) the maximal processing time (p max) ; and (iv) the maximal due date ( d max ). We use results from the literature to conclude that the problem is hard with respect to (wrt.) parameter υ d and is tractable (i.e., solvable in FPT time) wrt. p max . We then provide two FPT algorithms showing that the problem is also tractable wrt. to υ p and d max . We continue by analyzing a single-machine scheduling problem with assignable due dates where the cost function to be minimized includes penalties due to weighted early and tardy work. We assume that each job can be assigned a different due-date, the value of which is subject to a job-dependent upper bound. We provide an efficient method to optimally assign due dates for a given job schedule. We then use this result to reduce the problem to a purely combinatorial problem, which we show is N P -hard in general, but solvable in either FPT time or polynomial time for some special cases. [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling a set of direct deliveries between a depot and multiple customers using a given heterogeneous truck fleet. The trips have time windows and weights, and they should be completed as soon after release as possible (minimization of maximum weighted flow time). Moreover, some trips can optionally be combined in predefined milk runs (i.e., round trip tours), which need not be linear combinations of the constituent direct trips, accounting, e.g., for consolidation effects because the loading dock needs to be approached only once. This problem has applications, e.g., in just-in-time, humanitarian, and military logistics. We adapt a mixed-integer programming model from the literature to this problem and show that deciding feasibility is NP-complete in the strong sense on three levels: assigning trips to trucks, selecting milk runs, and scheduling trips on each individual truck. We also show that, despite this complexity, a state-of-the-art constraint programming solver and a problem-specific approach based on logic-based Benders decomposition can solve even large instances with up to 175 trips in many cases, while the mixed-integer programming model is essentially unsolvable using commercial optimization software. We also investigate the robustness of the maximum flow time objective in the face of unforeseen delays as well as the influence of milk runs. [ABSTRACT FROM AUTHOR]

In order for a system to stay operational, its components need maintenance. We consider two stakeholders—a system operator and a maintenance workshop—and a contract governing their joint activities. Components in the operating systems that are to be maintained are sent to the maintenance workshop, which should perform all maintenance activities on time in order to satisfy the contract. The maintained components are then sent back to be used in the operating systems. Our modeling of this system-of-systems includes stocks of damaged and repaired components, the workshop scheduling, and the planning of preventive maintenance for the operating systems. Our modeling is based on a mixed-binary linear optimization (MBLP) model of a preventive maintenance scheduling problem with so-called interval costs over a finite and discretized time horizon. We generalize and extend this model with the flow of components through the workshop, including the stocks of spare components. The resulting scheduling model—a mixed-integer optimization (MILP) model—is then utilized to optimize the main contract in a bi-objective setting: maximizing the availability of repaired (or new) components and minimizing the costs of maintaining the operating systems over the time horizon. We analyze the main contract and briefly discuss a turn-around time contract. Our results concern the effect of our modeling on the levels of the stocks of components over time, in particular minimizing the risk for lack of spare components. [ABSTRACT FROM AUTHOR]

In mass casualty incidents, patients need to be evacuated to nearby hospitals as soon as possible, and a surge in demand for emergency medical services then occurs. It would result in ambulance offload delays, i.e., no emergency operating room is available when the ambulance arrives at a hospital, and thus the patients cannot be treated immediately. In this paper, we aim to solve a combinatorial problem of patient-to-hospital assignment and patient surgery sequence considering patient deterioration and ambulance offload delay during a mass casualty incident. A mixed-integer programming model is proposed. The objective is to minimize the completion time of all patients' surgeries. For solving such a problem, some structural properties of our studied problem are derived, and a heuristic is developed to solve the single operating room scheduling problem considering ambulance offload delay and patient deterioration based on these structural properties. A hybrid Firefly Algorithm-Variable Neighborhood Search algorithm incorporating the heuristic method is proposed to solve it. Our proposed algorithm can solve the problem within a short computation time, and the computational results demonstrate the superiority of our proposed algorithm over the compared algorithms. [ABSTRACT FROM AUTHOR]

How to improve the efficiency of operating rooms (ORs) has always been a challenging problem in the context of healthcare operations management. This paper focuses on the research of operating room scheduling under non-operatingroomanesthesia (NORA) mechanism, in the presence of the uncertainty of emergency arrivals. In particular, we examine the advantages of the NORA mechanism in comparison with traditional surgical anesthesia practice under different operating room settings. Operationally, the process is comprised of two stages: (1) initial scheduling and (2) rescheduling. In the first stage, the initial schedule for elective surgeries under NORA is first performed through our developed model. With experiments, it is shown that for different operating room settings, the NORA mechanism can significantly improve the operating room utilization in comparison with the traditional OR anesthesia process. In the second stage of rescheduling, our experiment results show that the rescheduling model can effectively address the disruptions caused by the random arrival of emergency patients. [ABSTRACT FROM AUTHOR]

Scheduling aircraft turnarounds at airports requires the coordination of several organizations, including the airport operator, airlines, and ground service providers. The latter manage the necessary supplies and teams to handle aircraft in between consecutive flights, in an area called the airport 'apron'. Divergence and conflicting priorities across organizational borders negatively impact the smooth running of operations, and play a major role in departure delays. We provide a novel simulation-optimization approach that allows multiple service providers to build robust plans for their teams independently, whilst supporting overall coordination through central scheduling of all the involved turnaround activities. Simulation is integrated within the optimization process, following simheuristic techniques, which are augmented with an efficient search driving mechanism. Two tailored constraint-based feedback routines are automatically generated from simulation outputs to constrain the search space to solutions more likely to ensure plan robustness. The two simulation components provide constructive feedback on individual routing problems and global turnaround scheduling, respectively. Compared to the state-of-the-art approach for aircraft turnaround scheduling and routing of service teams, our methodology improves the apron's on-time punctuality, without the need for the involved organizations to share sensitive information. This supports a wider applicability of our approach in a multiple-stakeholder environment. [ABSTRACT FROM AUTHOR]

This paper addresses a parallel machine scheduling problem with non-anticipatory family setup times and batching, considering the task's stochastic processing times and release dates. The problem arises from a real-life ship scheduling problem in the oil and gas industry. We developed an Iterated Greedy simheuristic with built-in Monte Carlo Simulation to sample the stochastic parameters. We conducted experiments on a set of instances from the literature, considering two simheuristic variants and three uncertainty levels for the stochastic parameters. To highlight the advantages of using simulation to tackle the stochastic problem, the simheuristics are compared against a regular Iterated Greedy metaheuristic, yielding an improvement of up to 16.5% on the objective function's expected values, with a reduced impact on computational times. During a risk analysis, the Pareto set of solutions is generated to illustrate the trade-off between the expected objective value of the solutions and the conditional value at risk, providing decision-makers with a useful tool to select the schedules that better fit their risk profiles. We use an iterative mechanism to build confidence intervals within a certain confidence level during the method's simulation step, interrupting the procedure when it reaches the desired error. This strategy's advantage is highlighted in the computational experiments, which indicates that the number of replications of the simulation is instance and uncertainty level dependent. A periodic re-planning strategy is also used to evaluate the performance of the simheuristic, highlighting the advantages of using the proposed algorithm in a real-life usage situation. [ABSTRACT FROM AUTHOR]

This note presents a novel chemotherapy protocol for physicians to treat cancer tumors. Mathematical modeling, analysis, and simulations are used to describe the detailed dynamics of tumor, effector-immune cells, lymphocyte population, and chemotherapy drug, inside the patient body. An optimized scheduling alternating between treatment and relaxation sessions is determined to minimize the tumor size at the end of therapy period and overcome the toxicity level of patient's organs. To this end, we propose and allot relaxation sessions between two consecutive treatment sessions so that the body can partially recover. For each treatment period, we determine an optimal control strategy to minimize the tumor size and drug consumption without negatively affecting the natural cells. Finally, a particle swarm optimization-based approach is developed in order to ascertain the duration of each therapy session. The obtained results show that the proposed solution presents significant advantages in drug dosage, tumor reduction, and chemotherapy scheduling sessions compared to mathematical-based state-of-art approaches. [ABSTRACT FROM AUTHOR]

Time-relaxed sports timetables use more time slots than strictly needed, and are particularly popular in amateur (indoor) leagues. However, due to unexpected events, a considerable number of games may not be played as initially planned before the start of the tournament, leading to a potentially very different realized timetable. This study focuses on dealing with these uncertain events in time-relaxed round-robin sports timetabling, and how to mitigate their effect on the quality of the timetable. We use three quality measures to evaluate the time-relaxed timetables, namely, the games played difference index, the rest difference index and the number of cancelled games. We present several combined proactive and reactive approaches taking into account venue and team availability. Proactive strategies determine the position of time slots that are used as a buffer, while reactive strategies reschedule matches to these buffers in terms of the quality measures. [ABSTRACT FROM AUTHOR]

A recent Journal of Scheduling paper by Chen and Zhang (J Sched, 2020. https://doi.org/10.1007/s10951-020-00668-1) proves that the problem of scheduling coupled tasks to minimize total completion time is NP-hard in the strong sense even for the case with all tasks having the same, though not necessarily unit, processing times. This note shows a simpler proof of that result, and strengthens it by proving that the problem is NP-hard in the strong sense even if all tasks are unit-time. [ABSTRACT FROM AUTHOR]

This research focuses on studying the correlated parallel machine scheduling problem with release dates to minimize the number of tardy jobs and the total weighted completion time to find Pareto optima of all non-dominated solutions for both criteria. First, a mixed integer programming (MIP) model to find the entire efficient frontier for the studied problem has been proposed. Next, a bicriteria heuristic, named UTWC, and three artificial bee colony (ABC) variant algorithms have been proposed to tackle the studied problem. The three ABC variant algorithms are ABC, ABC with variable neighborhood search scheme (ABC_VNS), and ABC with simulated annealing scheme (ABC_SA). For small problem instances, we compare the proposed heuristic UTWC and three ABC variant algorithms with the efficient frontier generated by solving the MIP model. For large problem instances, we compare the UTWC and three ABC variant algorithms with an existing multi-objective tabu search algorithm (TSA). We create a reference set by combining the solutions from the three ABC variant algorithms and the TSA. The computational results indicate that the UTWC heuristic can find a set of non-dominated solutions that are uniformly distributed above the efficient frontier. The proposed ABC_VNS algorithm outperforms all the compared algorithms in both small and large problem instances. [ABSTRACT FROM AUTHOR]

This paper considers an integrated approach to two common problems in a precision agriculture framework: management zone delineation and selective harvest scheduling. Our model minimizes the total costs of harvest operations, establishing planning and scheduling for selective harvest of each selected management zone. Therefore, this tool provides important information for decision making of farmers in the field. Our integrated model is contrasted with the hierarchical approach commonly used in the literature for these cases, where the result of zoning problem is an input to schedule the harvest problem. Both problems were solved through a complete enumeration of all the potential management zones and demonstrated the advantages of our proposed model over the hierarchical approach. Our model reached an average reduction of 10% in harvest operations costs for different instances in a case study. [ABSTRACT FROM AUTHOR]

Optimizing maintenance scheduling is a major issue to improve the performance of hydropower plants. We study a system of several physical components of the same family: either a set of turbines, a set of transformers or a set of generators. The components share a common stock of spare parts and experience random failures that occur according to known failure distributions. We seek a deterministic preventive maintenance strategy that minimizes an expected cost depending on maintenance and forced outages of the system. The Auxiliary Problem Principle is used to decompose the original large-scale optimization problem into a sequence of independent subproblems of smaller dimension while ensuring their coordination. Each subproblem consists in optimizing the maintenance on a single component. Decomposition-coordination techniques are based on variational techniques but the maintenance optimization problem is a mixed-integer problem. Therefore, we relax the dynamics and the cost functions of the system. The resulting algorithm iteratively solves the subproblems on the relaxed system with a blackbox method and coordinates the components. Relaxation parameters have an important influence on the optimization and must be appropriately chosen. An admissible maintenance strategy is then derived from the resolution of the relaxed problem. We apply the decomposition algorithm on a system with 80 components. It outperforms the reference blackbox method applied directly on the original problem. [ABSTRACT FROM AUTHOR]

To improve the blood collection volume and reduce the staff costs, this study investigates the staff scheduling problem faced by blood donation center under variant situations derived from reality. Staff scheduling for blood donation center is a complex task due to the stochastic arriving of blood donors. In this study, we propose the deterministic demand model and stochastic demand model of blood donors according to the number of donors arriving at donation sites. Then, based on the deterministic demand and the stochastic demand models, we consider the number of staff in the blood donation center and group blood donation. Five blood collection scenarios are proposed using the combination of donors and staff. To solve the proposed models, linear transformation and lexicographic order optimal method are applied. To verify the effectiveness of the proposed models, both large-scale and small-scale numerical experiments are conducted and its the stability is also validated using the 10 times of random numerical experiments. All of the experimental results show that the proposed models need few staff when facing adequate staff scenarios, and reduce the number of donors when facing inadequate staff scenarios. [ABSTRACT FROM AUTHOR]

Over the past couple of centuries, with the increase in the significance of the railways to the economy, the complexity of the railway network and consequently the decision making involved and the number of problems faced has only increased. Among the host of problems in railways management, one of the most important is the locomotive assignment problem (LAP). The LAP is as old as the railways itself. The objective of the LAP is to assign a fleet of locomotives at minimum cost to pre-scheduled trains subject to a host of constraints. Most of the models in literature either work on improving the efficiency of solving the LAP or attempt to solve the three levels of LAP separately. Our attempt in this paper is to arrive at a linear mathematical model that integrates the strategic, tactical and operational level aspects of the LAP. We also demonstrate that by the addition of a valid inequality, the lower bounds can be improved substantially resulting in a substantial reduction in solution times for the problem instances. Further, we develop a Dijkstra's algorithm-based heuristic to test the problem instances and compare the solution times and quality of solutions. Finally, we develop a case based on Southern Zone of the Indian Railways and test the heuristic to solve the LAP for this zone. [ABSTRACT FROM AUTHOR]

This paper proposes two models for the Technician Routing and Scheduling Problem (TRSP), which are motivated by a telecom provider based in Saskatchewan, Canada. The proposed TRSP models are distinguished from existing models by their ability to address two key issues: overnight and lunch break scheduling. The models aim to scheduling a set of technicians with homogeneous skill levels and different working hours for the purpose of providing services with different service times and time windows to a diverse set of widely spread communities. As the large-sized experiments of this problem categorized into NP-hard problems, a metaheuristic-based technique, Invasive Weed Optimization, is developed to solve them. A comparative analysis is performed to choose the optimum TRSP model based on two factors which are distance of communities to the main depot and balanced service times during planning horizon. The performance of the models is evaluated through the real-world data obtained from the telecom provider. The results prove that the overnight TRSP model is capable of substantially decreasing travel costs and the number of technicians that are required to perform the same set of services. [ABSTRACT FROM AUTHOR]

Operating Room (OR) management has been among the mainstream of hospital management research, as ORs are commonly considered as one of the most critical and expensive resources. The complicated connection and interplay between ORs and their upstream and downstream units has recently attracted research attention to focus more on allocating medical resources efficiently for the sake of a balanced coordination. As a critical step, surgical scheduling in the presence of uncertain surgery durations is pivotal but rather challenging since a patient cannot be hospitalized if a recovery bed will not be available to accommodate the admission. To tackle the challenge, we propose an overflow strategy that allows patients to be assigned to an undesignated department if the designated one is full. It has been proved that overflow strategy can successfully alleviate the imbalance of capacity utilization. However, some studies indicate that implementation of the overflow strategy exacerbates the readmission rate as well as the length of stay (LOS). To rigorously examine the overflow strategy and explore its optimal solution, we propose a Fuzzy model for surgical scheduling by explicitly considering downstream shortage, as well as the uncertainty of surgery duration and patient LOS. To solve the Fuzzy model, a hybrid algorithm (so-called GA-P) is developed, stemming from Genetic Algorithm (GA). Extensive numerical results demonstrate the plausible efficiency of the GA-P algorithm, especially for large-scale scheduling problems (e.g., comprehensive hospitals). Additionally, it is shown that the overflow cost plays a critical role in determining the efficiency of the overflow strategy; viz., benefits from the overflow strategy can be reduced as the overflow cost increases, and eventually almost vanishes when the cost becomes sufficiently large. Finally, the Fuzzy model is tested to be effective in terms of simplicity and reliability, yet without cannibalizing the patient admission rate. [ABSTRACT FROM AUTHOR]

Oil palm agricultural systems involve large extensions of land that demand careful planning of the harvesting operations. The plantation manager is in charge of synchronizing resources (i.e., crews and a complex cableway network) to harvest at the right time to maximize palm oil yield in latter stages of the value chain. In particular, in this type of crop it is ideal to visit each palm every eight to twelve days to avoid loose fruit picking, over-ripeness, or rotten fruit harvesting. To optimize harvest operations, we propose an end-to-end analytics solution involving data treatment, descriptive (simulation), and prescriptive models (optimization) in this agricultural system. At the core of our approach lies a set of interconnected models that use optimization, heuristic techniques, and simulation. These models cover strategic (harvest cycle), tactical (resource allocation), and operational (transport allocation) decisions. We present a case study of a 2000-ha plantation located in the Colombian Orinoquia. The results show a strong potential for improving yield by reducing the harvest cycle length from 19.6 to 8.3 days. [ABSTRACT FROM AUTHOR]

This paper concentrates on the divisional seru scheduling and worker assignment joint decision-making problem, and synthetically considers the difference in workers’ skill sets, the diversity of workers’ skill levels, the process sequence constraints, setup time, lot-splitting, etc., and then a nonlinear integer programming model is constructed to minimize the makespan. We show that it is necessary to consider the process sequence constraints, and the optimal makespan of the worker-operation allocation scheme without considering the process sequence constraints is much larger than that of considering the process sequence constraints. Moreover, as the number of workers increases, the advantage of considering sequence constraints becomes more obvious. Considering the multi-decision attributes and intractable computations of the studied problem, we turn it into bi-level programming. Then based on the combination of a hybrid genetic variable neighbourhood search algorithm (HGVNSA) and a greedy heuristic algorithm (GHA), a bi-level nested heuristic algorithm (HGVNSA-GHA) is designed. Finally, numerical experiment results show that the proposed algorithm can achieve better results and higher efficiency for the divisional seru scheduling and worker assignment model. [ABSTRACT FROM AUTHOR]

Mathematical programming techniques are used in a tool developed to solve a real unrelated parallel machine problem in a bottle closures manufacturing plant. The tool is able to define the production process planning for a scheduling horizon of up to one month while satisfying all relevant constraints. The planning problem is a multi-objective one of minimizing production completion times, overproduction and machine idle time. Due to the problem’s complexity, the approach adopted for obtaining good solutions in reasonable execution times is based on dividing it into three subproblems or stages, each solved by a different MILP model. In the first stage, the model performs a lexicographic minimization to assign closure injection molds to the plant’s machines; in the second stage, the model corrects the machine stoppage times for mold changes; and in the third stage, the model determines the assignment of different colors to the closures or its parts produced with a given mold. Results are presented for instances of up to 100 jobs, showing how different characteristics of the problem influence the performance of the proposed solution approach. A comparison is also presented between our model’s result and the manual scheduling carried out by the factory staff for a real instance, demonstrating that our method enabled significant enhancements in the aforementioned objectives. [ABSTRACT FROM AUTHOR]

This paper addresses the class of permutation flow shop scheduling where jobs, after their completion, must be grouped in batches. This is a common scheme in industrial environments, where products undergo multiple process steps in different shops and, when completed, must be transported to customers or the next production step. A new optimisation criterion is used, the inter-exit time, i.e., the difference between the completion times of two jobs. An upper bound is proposed and demonstrated for a general permutation flow shop with m machines. [ABSTRACT FROM AUTHOR]

In this paper, we study the construction of a cyclic appointment schedule in an outpatient department. In particular, we determine the capacity distribution between elective and urgent patients and the scheduling of the time slots reserved for these patients such that the operational waiting times of elective and urgent patients are minimised. The proposed solution methodology devises a Pareto set of cyclic appointment schedules based on these waiting times with different capacity allocations for urgent patients. An approximation of the Pareto set of non-dominated schedules is obtained using a multi-objective archived simulated annealing heuristic. To accurately validate the cyclic appointment schedules, we incorporate operational decision-making via scheduling individual patients. To this end, we simulate operational variability, i.e., patient arrivals, no-show behaviour, punctuality and scan durations, based on real-life input data. The patients are assigned one-by-one using an online scheduling rule. Computational experiments are conducted with a real-life case study. We compare different appointment scheduling rules and discuss the impact of the capacity distribution between elective and urgent patients and the timing of urgent slots in the cyclic appointment schedules. The results show that the distribution of capacity between patient types, the timing of urgent slots and appointment rules all have significant impacts on patient waiting times. Appointment waiting times improve when urgent slots are spread equally over and throughout the days considered and when the Bailey–Welch rule is used to schedule patients. Trade-offs between elective and urgent waiting times resulting from different capacity distributions or slot timing are exemplified via a Pareto front. The proposed method outperforms relevant single-pass methodologies, and we demonstrate that its performance is strengthened thanks to the integrated optimisation of strategic, tactical and operational decisions. [ABSTRACT FROM AUTHOR]

The objective of the Patrol Boat Scheduling Problem with Complete Coverage (PBSPCC) is to find a minimum size patrol boat fleet to provide continuous coverage at a set of maritime patrol regions, ensuring that there is at least one vessel on station in each patrol region at any given time. The requirement for continuous patrol coverage is complicated by the need for vessels to be replenished on a regular basis. This combinatorial optimization problem contains both routing and scheduling components and is known to be NP-hard. In this paper, we show how recent theoretical insights can be used in conjunction with specially tailored heuristics to accelerate a column generation solution approach over a resource-space-time network construct. We show how the column generation approach can be used within a branch-and-price framework and combined with various reduction techniques to find cyclic and long-term scheduling solutions on a range of test problems. [ABSTRACT FROM AUTHOR]

It has been proposed that if replacement time is planned too early prior to failure, a waste of operation cost, i.e., excess costs, would incur because the system might run for an additional period of time to complete critical operations, and if replacement time is too late after failure, a great failure cost, i.e., shortage cost, is incurred due to the delay in time of the carelessly scheduled replacement. In order to make the preventive replacement policies perform in a more general way, the above two variable types of costs are taken into considerations for periodic replacement policies in this paper. We firstly take up a standard model in which the unit is replaced preventively at periodic times. Secondly, the modeling approaches of whichever occurs first and last are applied into periodic and random models, and replacement first and last policies are discussed to find optimum periodic replacement times for a random working time. Furthermore, optimum working numbers are obtained for the extended models. We give analytical discussions of the above replacement policies, and finally, numerical examples are illustrated. [ABSTRACT FROM AUTHOR]

We focus on the lot-sizing and scheduling problem with the additional considerations of machine eligibility, sequence-dependent setups, and uncertain demands. Multi-stage stochastic programming is proposed. We analyze the problem structure and suggest ways for modeling and solving large-scale stochastic integer programs. The analysis compares deterministic and stochastic model solutions to assess demand variance effects under the circumstances of increasing, fluctuating, and decreasing demands. The result shows that the expected cost performance of the stochastic programming model outperforms that of the deterministic model, in particular, when the demand is highly uncertain in the circumstance of an upward market trend. Our study can apply to the wafer fab manufacturing and other industries that heavily restricted by machine eligibility and demand uncertainties. [ABSTRACT FROM AUTHOR]

Multi-position refining furnaces are a critical strategy for energy-intensive industries to meet its demands of fast-paced production. In most literature, however, they serve only as a buffer, holding up to at most two ladles to maintain the proper temperature of ladles. These studies do not take full advantage of them, nor do they study the production scheduling of energy-intensive enterprises with multi-position refining furnaces under time-of-use (TOU) tariffs. Therefore, this paper presents a steelmaking-continuous casting (SCC) scheduling problem with multi-position refining furnaces under TOU tariffs. We firstly develop a mixed integer nonlinear programming (MINLP) model with the goals of minimizing jobs completion time, machines idle time, and total electricity costs, which subjects to the double-position characteristics and other process constraints. Owing to the complexity between the time-slots of TOU tariffs and the processing cycles of jobs, we design an intermediate function to calculate objectives efficiently. Furthermore, a Lagrangian relaxation (LR) algorithm based on a subgradient algorithm is utilized to solve the proposed model, and an interior point algorithm is adopted to solve sub-problems obtained by job-level and batch-level decomposition, whose solution approximates optimality comparing to GUROBI solver. The computational results demonstrate that the solution of job-level decomposition algorithm approximates the optimal scheduling scheme in an acceptable time and is superior to that of GUROBI solver. In addition, double-position instance can find a better scheduling scheme than nondouble-position one. [ABSTRACT FROM AUTHOR]

During peak-hour busy airports have the challenge of turning aircraft around as quickly as possible, which includes sequencing their landings and take-offs with maximum efficiency, without sacrificing safety. This problem, termed aircraft sequencing problem (ASP) has traditionally been hard to solve optimally in real-time, even for flights over a one-hour planning window. In this article, we present a novel data-splitting algorithm to solve the ASP on a single runway with the objective to minimize the total delay in the system both under segregated and mixed mode of operation. The problem is formulated as a 0–1 mixed integer program, taking into account several realistic constraints, including safety separation standards, wide time-windows, and constrained position shifting. Following divide-and-conquer paradigm, the algorithm divides the given set of flights into several disjoint subsets, each of which is optimized using 0–1 MIP while ensuring the optimality of the entire set. One hour peak-traffic instances of this problem, which is NP-hard in general, are computationally difficult to solve with direct application of the commercial solver, as well as existing state-of-the-art dynamic programming method. Using our data-splitting algorithm, various randomly generated instances of the problem can be solved optimally in near real-time, with time savings of over 90%. [ABSTRACT FROM AUTHOR]

Mixed-criticality scheduling addresses the problem of sharing common resources among jobs of different degrees of criticality and uncertain processing times. The processing time of jobs is observed during the online execution of the schedule with the prolongations of critical jobs being compensated by the rejection of less critical ones. One of the central questions in the field of mixed-criticality scheduling is ensuring the high reliability of the system with as few resources as possible. In this paper, we study the computation of the execution probability of jobs with uncertain processing times in a static mixed-criticality schedule. The aim is to compute the execution probability of jobs (i.e., the objective function of a schedule), which is a problem solvable by a closed-form formula when the jobs are not replicated. We introduce the job replication, i.e., scheduling a single job multiple times, as a new mechanism for increasing the execution probability of jobs. We show that the general problem with job replication becomes # P -hard, which is proven by the reduction from the counting variant of 3-sat problem. To compute the execution probability, we propose an algorithm utilizing the framework of Bayesian networks. Furthermore, we show that cases of practical interest admit a polynomial-time algorithm and are efficiently solvable. The proposed methodology demonstrates an interesting connection between schedules with uncertain execution and probabilistic graphical models and opens a new approach to the analysis of mixed-criticality schedules. [ABSTRACT FROM AUTHOR]

In a recent study, Sun et al. (AOR 292:113–131, 2020) studied due-window proportionate flow shop scheduling problems with position-dependent weights. For common due-window (denoted by CONW) and slack due-window (denoted by SLKW) assignment methods, they proved that these two problems can be solved in O (n 2 log n) time respectively, where n is the number of jobs. In this paper, we consider the same problems, and our contribution is that the CONW problem can be optimally solved by a lower-order algorithm, which runs in O (n log n) time, implying an improvement of a factor of n. [ABSTRACT FROM AUTHOR]

In enterprise project management systems, a program at the tactical level coordinates and manages multiple projects at the operational level. There are close relationships between multiple projects in a program, which are typically manifested as shared resources and precedence relationships. Most research efforts have concentrated on the resource sharing by projects, while the precedence relationships between projects have yet to be comprehensively investigated. In this paper, a bi-objective hierarchical resource-constrained program scheduling problem proposed, where both resource sharing and precedence relationships between projects are considered in a distributed environment. The problem contains two different sub-problems at the operational level and the tactical level, and they are modeled in the same way as two bi-objective multi-mode scheduling problems. Shared resources are allocated from the tactical level to the operational level, and once they are allocated to a project, they can only be re-allocated to other projects once the current project is finished. Subsequently, a two-phase algorithm based on NSGA-III is developed. The algorithm runs at the operational level and the tactical level in turn. According to the Pareto fronts of projects that are submitted from the operational level, the bi-objective program planning at the tactical level is conducted under the constraints of precedence relationships and shared resources. The results of computational simulations demonstrate the satisfactory performance of the improved algorithm. By coordinating the local optimization of projects and the global optimization of the program in a hierarchical framework, the method proposed in this paper provides an effective integrated scheduling method for decision-makers at various levels of a program. [ABSTRACT FROM AUTHOR]

This paper addresses the triangle width problem, which generalizes the classic two-machine flexible job-shop problem (FJSP) with tooling constraints. This new problem can be studied from three different angles: scheduling, matrix visualization, and vertex ordering in hypergraphs. We prove the equivalence of the different formulations of the problem and use them to establish the NP\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mathcal{N}\mathcal{P}$$\end{document}-Hardness and polynomiality of several of its subcases. This problem allows us to find more elegant (and probably shorter) proofs for several combinatorial problems in our analysis setting. Our study provides an elegant generalization of Johnson’s argument for the two-machine flow shop. It also shows the relation between the question: “Is a matrix triangular?” and the “k-visit of a graph”. [ABSTRACT FROM AUTHOR]

We consider the problem of a project manager of a matrix organization responsible for the timely completion of projects arriving over time and requiring the usage of a set of resources under his/her purview. A project is defined by a set of activities, precedence relations between activities, resource requirements, a customer due date, and a priority (a weight). Arriving projects are released to a flow control system that monitors the progress of activities and schedules the set of available activities, i.e., activities that are ready to be processed, as appropriate. A critical feature of such control systems is the decision process for choosing the next activity to seize a given resource. This is the focus of this paper. In the past several decades, various heuristic priority rules have been proposed in the literature to support this type of decision in differing settings such as the job shop problem and the deterministic resource-constrained project scheduling problem. A gap exists with respect to testing the various rules all together in the more realistic dynamic-stochastic multi-project environment when the objective is to minimize weighted project tardiness. The purpose of this paper is to fill this gap. Results show that the priority rule “Weighted Critical Ratio and Shortest Processing Time” (W(CR+SPT))\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(\hbox {W}(\hbox {CR}+\hbox {SPT}))$$\end{document} is the best performing rule with respect to minimizing weighted project tardiness. W(CR+SPT)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\hbox {W}(\hbox {CR}+\hbox {SPT})$$\end{document} is shown to be a variant of the family of “Modified Due Date” rules first introduced by Baker and Bertrand (J Oper Manage 1(3):37–42, 1982). Repeated application of Duncan’s Multiple Range test demonstrates the robustness of our findings. For the environmental parameters (due date tightness, variation of expected activity durations, and utilization of resource), the W(CR+SPT)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\hbox {W}(\hbox {CR}+\hbox {SPT})$$\end{document} rule is dominant with respect to weighted project tardiness among the eleven priority rules tested. Only when the number of resources is very modest (either 1 or 3 resources) or under a purely parallel resource network is W(CR+SPT)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\hbox {W}(\hbox {CR}+\hbox {SPT})$$\end{document} not the dominant rule. In those cases, its variant W(CR+GSPT)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\hbox {W}(\hbox {CR}+\hbox {GSPT})$$\end{document} is the best performing rule with respect to weighted project tardiness. [ABSTRACT FROM AUTHOR]

This paper addresses a multi-skill resource-constrained multi-project scheduling problem (MSRCMPSP) with different types of resources and complex industrial constraints, which originates from SNCF heavy maintenance factories. Two objective functions, that have been rarely addressed in the literature, are independently considered: (i) Minimization of the sum of the weighted tardiness of the projects and (ii) Minimization of the sum of the weighted duration of the projects. A time-indexed mixed-integer linear programming model is presented with both resource assignment and capacity constraints. To solve large instances with several thousand activities, a new memetic algorithm combining a novel hybrid simulated genetic algorithm with a simulated annealing is implemented. The memetic algorithm is compared with popular solution approaches. Computational experiments conducted on real instances and benchmark instances validate the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The online version of the original article can be found at https://doi.org/10.1007/s10479-023-05470-8.Annals of Operations Researchhttps://doi.org/10.1007/s10479-023-05470-8Due to proofing error during typesetting Figs. 3, 4 and 5 were left blank, published with black bar and has now been updated.Original article has been updated.Publisher's NoteSpringer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.By Rob Van Eynde; Mario Vanhoucke and José CoelhoReported by Author; Author; Author [Extracted from the article]

In the literature on multi-scenario scheduling problems, it is assumed that (i) each scenario defines a different possible realization of the job's parameters; and (ii) the value of each parameter is arbitrary for any job in any scenario. Under these assumptions many multi-scenario scheduling problems have been proven to be NP -hard. We study a special case of this set of problems, in which there is an agreeable condition between scenarios on the processing-time parameters. Accordingly, the processing time of job J j under scenario s i is at most its value under scenario s i + 1 , for i = 1 , ... q - 1 , where q is the number of different possible scenarios. We focus on three classical scheduling problems for which the single-scenario case is solvable in polynomial time, while the multi-scenario case is NP -hard, even when there are only two scenarios. The three scheduling problems consist of minimizing either the total completion time or the number of tardy jobs on a single machine, and minimizing the makespan in a two-machine flow-shop system. We show that the multi-scenario version of all three problems remains NP -hard even when processing times are agreeable and there are only two scenarios. We also show that for a more specific structure of job processing times two out of the three problems become easy to solve, while the complexity status of the third remains open for future research. [ABSTRACT FROM AUTHOR]

Appointment scheduling assigns start times in a session or consultation block to a set of tasks that share a common resource. For a generic repeated appointment scheduling problem, we study the trade-off between waiting for an appointment and waiting at the appointed time. Assuming that being scheduled later during a session implies that one has to wait longer for service (on average), it is often beneficial to choose a consultation block further away. We study this trade-off both when the patients have no information on how many patients are already scheduled in future consultation blocks and when they can observe the future block schedules. By some numerical examples, we find that in both cases the rational choice considerably changes between consecutive appointment blocks, patients favouring later blocks when the next appointment block starts in the near future. We also compare the rational choice with the socially optimal schedule and find that socially optimal scheduling can significantly reduce the waiting cost. [ABSTRACT FROM AUTHOR]

Limiting flight delays during operations has become a critical research topic in recent years due to their prohibitive impact on airlines, airports, and passengers. A popular strategy for addressing this problem considers the uncertainty of day-of-operations delays and adjusts flight schedules to accommodate them in the planning stage. In this work, we present a stochastic programming model to account for uncertain future delays by adding buffers to flight turnaround times in a controlled manner. Specifically, our model adds slack to flight connection times with the objective of minimizing the expected value of the total propagated flight delay in a schedule. We also present a parallel solution framework that integrates an outer approximation decomposition method and column generation. Further, we demonstrate the scalability of our approach and its effectiveness in reducing delays with an extensive simulation study of five different flight networks using real-world data. [ABSTRACT FROM AUTHOR]

We extend two classical scheduling and due-date assignment models. In the first (known in the literature as DIF), due-dates are determined by penalties for exceeding pre-specified deadlines. In the second (known as SLK), due-dates are assigned to jobs as a (linear) function of their processing times. We focus on the minmax versions of these models, and extend the single machine versions to a two-machine flowshop. We further extend the settings to that of a due-window. All the problems studied in this note are shown to have polynomial time solutions. [ABSTRACT FROM AUTHOR]

This paper introduces the d-distance matching problem, in which we are given a bipartite graph G = (S , T ; E) with S = { s 1 , ⋯ , s n } , a weight function on the edges and an integer d ∈ Z + . The goal is to find a maximum-weight subset M ⊆ E of the edges satisfying the following two conditions: (i) the degree of every node of S is at most one in M, (ii) if s i t , s j t ∈ M , then | j - i | ≥ d . This question arises naturally, for example, in various scheduling problems. We show that the problem is NP-complete in general and admits a simple 3-approximation. We give an FPT algorithm parameterized by d and also show that the case when the size of T is constant can be solved in polynomial time. From an approximability point of view, we show that the integrality gap of the natural integer programming model is at most 2 - 1 2 d - 1 , and give an LP-based approximation algorithm for the weighted case with the same guarantee. A combinatorial (2 - 1 d) -approximation algorithm is also presented. Several greedy approaches are considered, and a local search algorithm is described that achieves an approximation ratio of 3 / 2 + ϵ for any constant ϵ > 0 in the unweighted case. The novel approaches used in the analysis of the integrality gap and the approximation ratio of locally optimal solutions might be of independent combinatorial interest. [ABSTRACT FROM AUTHOR]

We consider a natural generalization of classical scheduling problems to a setting in which using a time unit for processing a job causes some time-dependent cost, the time-of-use tariff, which must be paid in addition to the standard scheduling cost. We focus on preemptive single-machine scheduling and two classical scheduling cost functions, the sum of (weighted) completion times and the maximum completion time, that is, the makespan. While these problems are easy to solve in the classical scheduling setting, they are considerably more complex when time-of-use tariffs must be considered. We contribute optimal polynomial-time algorithms and best possible approximation algorithms. For the problem of minimizing the total (weighted) completion time on a single machine, we present a polynomial-time algorithm that computes for any given sequence of jobs an optimal schedule, i.e., the optimal set of time slots to be used for preemptively scheduling jobs according to the given sequence. This result is based on dynamic programming using a subtle analysis of the structure of optimal solutions and a potential function argument. With this algorithm, we solve the unweighted problem optimally in polynomial time. For the more general problem, in which jobs may have individual weights, we develop a polynomial-time approximation scheme (PTAS) based on a dual scheduling approach introduced for scheduling on a machine of varying speed. As the weighted problem is strongly NP-hard, our PTAS is the best possible approximation we can hope for. For preemptive scheduling to minimize the makespan, we show that there is a comparably simple optimal algorithm with polynomial running time. This is true even in a certain generalized model with unrelated machines. [ABSTRACT FROM AUTHOR]

In this paper we introduce a complex scheduling problem that arises in a real-world industrial test laboratory, where a large number of activities has to be performed using qualified personnel and specialized equipment, subject to time windows and several other constraints. The problem is an extension of the well-known Resource-Constrained Project Scheduling Problem and features multiple heterogeneous resources with very general availability restrictions, as well as a grouping phase, where the jobs have to be assembled from smaller units. We describe an instance generator for this problem and publicly available instance sets, both randomly generated and real-world data. Finally, we present and evaluate different metaheuristic approaches to solve the scheduling subproblem, where the assembled jobs are already provided. Our results show that Simulated Annealing can be used to achieve very good results, in particular for large instances, where it is able to consistently find better solutions than a state-of-the-art constraint programming solver within reasonable time. [ABSTRACT FROM AUTHOR]