Lecture Notes in Computational Science and Engineering

Twice a year, the regional school departments in Norway need to schedule examination sessions for external candidates in the region, which also involves reserving and assigning rooms, examiners and reviewers. We present a cut-and-branch algorithm to get provably good solutions to this problem, the external candidates examination scheduling problem (ExtSchedule). The algorithm relies on a new family of valid inequalities, effective in tightening the initial formulation and accelerating the solution process. We develop an efficient separation algorithm and embed it in a cut-and-branch framework to solve the problem. The algorithm has been validated on real-life instances arising from the Vestfold County school department in Norway.

Abstract The task of scheduling jobs to machines while minimizing the total makespan, the sum of weighted completion times, or a norm of the load vector are among the oldest and most fundamental tasks in combinatorial optimization. Since all of these problems are in general -hard, much attention has been given to the regime where there is only a small number k of job types, but possibly the number of jobs n is large; this is the few job types, high-multiplicity regime. Despite many positive results, the hardness boundary of this regime was not understood until now. We show that makespan minimization on uniformly related machines ( $$Q|HM|C_{\max }$$ Q | H M | C max ) is -hard already with 6 job types, and that the related Cutting Stock problem is -hard already with 8 item types. For the more general unrelated machines model ( $$R|HM|C_{\max }$$ R | H M | C max ), we show that if the largest job size $$p_{\max }$$ p max or the number of jobs n is polynomially bounded in the instance size |I|, there are algorithms with complexity $$|I|^{{{\,\mathrm{\textrm{poly}}\,}}(k)}$$ | I | poly ( k ) . Our main result is that this is unlikely to be improved because $$Q||C_{\max }$$ Q | | C max is $$\mathsf {W[1]}$$ W [ 1 ] -hard parameterized by k already when n, $$p_{\max }$$ p max , and the numbers describing the machine speeds are polynomial in |I|; the same holds for $$R||C_{\max }$$ R | | C max (without machine speeds) when the job sizes matrix has rank 2. Our positive and negative results also extend to the objectives $$\ell _2$$ ℓ 2 -norm minimization of the load vector and, partially, sum of weighted completion times $$\sum w_j C_j$$ ∑ w j C j . Along the way, we answer affirmatively the question whether makespan minimization on identical machines ( $$P||C_{\max }$$ P | | C max ) is fixed-parameter tractable parameterized by k, extending our understanding of this fundamental problem. Together with our hardness results for $$Q||C_{\max }$$ Q | | C max , this implies that the complexity of $$P|HM|C_{\max }$$ P | H M | C max is the only remaining open case.

AbstractThis paper considers a recoverable robust single-machine scheduling problem under polyhedral uncertainty with the objective of minimising the total flow time. In this setting, a decision-maker must determine a first-stage schedule subject to the uncertain job processing times. Then following the realisation of these processing times, they have the option to swap the positions of up to $$\Delta $$ Δ disjoint pairs of jobs to obtain a second-stage schedule. We first formulate this scheduling problem using a general recoverable robust framework, before we examine the incremental subproblem in further detail. We prove a general result for max-weight matching problems, showing that for edge weights of a specific form, the matching polytope can be fully characterised by polynomially many constraints. We use this result to derive a matching-based compact formulation for the full problem. Further analysis of the incremental problem leads to an additional assignment-based compact formulation. Computational results on budgeted uncertainty sets compare the relative strengths of the three compact models we propose.

The performance of safety-critical systems implemented on multi-core platforms depends heavily on the scheduling mechanism used. This paper addresses the problem of multi-core scheduling of a real-time application modelled as a Directed Acyclic Graph (DAG) with multiple service levels (where, a higher service level implies higher Quality-of-Service (QoS)), by proposing a novel two-phase offline–online scheduling mechanism called HYBRID-SCHED. The offline phase constructs a static schedule assuming worst-case execution behaviour, in order to ensure desired predictability with a minimum guaranteed QoS under all possible execution scenarios. Two alternative offline solution strategies have been designed. While the first strategy is a fast but reasonably good heuristic solution called Service-level Aware Scheduler (SAS), the second is a branch-and-bound based optimal solution-space search technique. However, online execution based on strict adherence to the static schedule may result in poor resource utilization as actual execution time of tasks at run time may be significantly less than worst-case estimates. In order to improve the situation, an online scheduler called Actual Execution-time Aware Scheduler (AEAS) has been developed. The basic goal of AEAS is to strategically reclaim resources that were provided for tasks at design time but are in fact being used inactively at run time. By gradually raising the service levels of the remaining (yet-to-be-completed) jobs, AEAS can then use the recovered resources to improve system-level QoS. Using real-world benchmark applications, we assessed the performance of the suggested framework. Results obtained demonstrate the usefulness of our plan.

AbstractIn this paper, we reconsider an offline load-balancing problem with unit-time jobs that require one unit from a common resource throughout their execution. In the unit-time case, the jobs have to be assigned to time-slots such that a separable convex function of the load of the resource has to be minimized. Variants of this problem have been studied extensively in the literature under different names. We briefly discuss these problems and give a new implementation for one of them with a better worst-case time complexity than any of the known methods. We also consider the more general preemptive problem in which the execution of the jobs can be interrupted and resumed later. Furthermore, we divide the time horizon into disjoint time intervals, and for each interval, a separable convex cost function is given. The jobs have to be scheduled within their feasible intervals preemptively such that the total cost is minimized, where the cost is determined separately for each interval by the corresponding cost function. We show how to solve this problem in polynomial time by a single minimum-cost-flow computation. For the preemptive problem with one cost function only, we propose a proprietary algorithm for finding a feasible solution which is optimal for any convex cost function. We also present some qualitative computational results.

AbstractWith ever-rising student numbers and an increasing shift towards more interdisciplinary study programs, the requirements for finding schedules for courses and exams become ever more complex. In real-world scenarios, the models used for calculating solutions to the course and the examination timetabling problem often must be provided to the students at the time of registration. In the field of curriculum-based course timetabling, timetables are calculated based on the structure of the study programs. For the examination timetabling problem, only a few papers focus on scheduling exams without registration data, as the requirements for exams are often more strict, or partial information is known from course registrations. In this paper we show that with the use of robustness techniques, we can also define the examination timetabling problem based on curricula. We introduce three robustness measures that address the inherent uncertainty when using the curriculum-based model. These robustness measures, along with other quality measures, are analyzed using a multi-objective simulated annealing algorithm. The results are compared on the Pareto front approximations found. We present a case study showing that, without a significant loss in solution quality, the chance is significantly reduced that rescheduling will be required after the exact numbers for the model are known.

This paper mainly focuses on a resource leveling variant of a two-processor scheduling problem. The latter problem is to schedule a set of dependent UET jobs on two identical processors with minimum makespan. It is known to be polynomial-time solvable. In the variant we consider, the resource constraint on processors is relaxed and the objective is no longer to minimize makespan. Instead, a deadline is imposed on the makespan and the objective is to minimize the total resource use exceeding a threshold resource level of two. This resource leveling criterion is known as the total overload cost. Sophisticated matching arguments allow us to provide a polynomial algorithm computing the optimal solution as a function of the makespan deadline. It extends a solving method from the literature for the two-processor scheduling problem. Moreover, the complexity of related resource leveling problems sharing the same objective is studied. These results lead to polynomial or pseudo-polynomial algorithms or NP-hardness proofs, allowing for an interesting comparison with classical machine scheduling problems.

Scientific workflows are large applications that consist of smaller computational units called tasks that have data dependency on each other. The tasks of a workflow can be scheduled and executed on distributed resources in a parallel manner. Cloud computing offers distributed, scalable, virtualized, cost-effective computing environments making them ideal platforms to execute scientific workflows. Cloud services provide their users with a vision of an unlimited amount of computing resources. However, considering different types of resources and QoS requirements, the problem of workflow scheduling lies in the NP-complete class. Thus, numerous types of research have been conducted in this area during the past years. In this paper, we aim to provide a comprehensive study of the workflow scheduling problem, existing solutions, and available tools that can be used by researchers in this domain. First, we present a taxonomy on scheduling algorithms and examine the existing works from different perspectives from application and resource models to algorithms’ objectives and their nature. We also have presented a taxonomy of evaluation data sets as well as simulation tools and their architecture since the evaluation of an algorithm is important and must be performed accurately. Next, we survey some of the most recent works in the context of the proposed taxonomy with a focus on emerging cloud services like serverless computing or workflow as a service platform and state-of-the-art scheduling approaches. Moreover, we discuss some of the existing gaps in the literature and identify possible research directions that can be seen as potential contributions to future developments.

AbstractTo streamline their fulfillment processes, many e-commerce retailers today use automated packaging machines for their outbound parcels. An important performance–waste tradeoff is associated with these machines: To reduce packaging waste when handling different sized goods, packaging machines should be able to handle different carton sizes. However, more carton sizes lead to a more involved scheduling process, so that the throughput performance deteriorates (and vice versa). To investigate this tradeoff, this paper develops scheduling procedures for a specific type of packaging machine, called blocking machines. These packaging machines provide multiple back-to-back packaging devices, each continuously processing a dedicated carton size, but blocking each other whenever incoming goods are not properly ordered according to carton sizes on the infeed conveyor. To reduce the resulting throughput loss, we derive various scheduling problems for optimizing the inflow of goods, provide a thorough analysis of the computational complexity, and derive an exact dynamic programming approach that is polynomial in the number of orders to be packed. This allows us to solve even large real-world instances to proven optimality with which we can analyze the performance–waste tradeoff of blocking machines.

AbstractIn this paper, we consider single-machine scheduling with multiple due dates per job. This is motivated by several industrial applications, where it is not important by how much we miss a due date. Instead the relevant objective is to minimize the number of missed due dates. Typically, this situation emerges whenever fixed delivery appointments are chosen in advance, such as in the production of individualized pharmaceuticals or when customers can only receive goods at certain days in the week, due to constraints in their warehouse operation. We compare this previously unexplored problem with classical due date scheduling, for which it is a generalization. We show that single-machine scheduling with multiple due dates is NP-hard in the strong sense if processing times are job dependent. If processing times are equal for all jobs, then single-machine scheduling with multiple due dates is at least as hard as the long-standing open problem of weighted tardiness with equal processing times and release dates $$1 \mid r_j, p_j = p \mid \sum w_j T_j$$ 1 ∣ r j , p j = p ∣ ∑ w j T j . Finally, we focus on the case of equal processing times and provide several polynomially solvable special cases as well as an exact branch-and-bound algorithm and heuristics for the general case. Experiments show that our branch-and-bound algorithm compares well to modern exact methods to solve problem $$1 \mid r_j, p_j = p \mid \sum w_{j} T_{j}$$ 1 ∣ r j , p j = p ∣ ∑ w j T j .

Abstract The $$1\vert \text {s-batch}(\infty ),r_j\vert \sum w_jU_j$$ 1 | s-batch ( ∞ ) , r j | ∑ w j U j scheduling problem takes as input a batch setup time $$\Delta $$ Δ and a set of n jobs, each having a processing time, a release date, a weight, and a due date; the task is to find a sequence of batches that minimizes the weighted number of tardy jobs. This problem was introduced by Hochbaum and Landy (Oper Res Lett 16(2):79–86, 1994); as a wide generalization of Knapsack, it is $$\textsf{NP}$$ NP -hard. In this work, we provide a multivariate complexity analysis of the $$1\vert \text {s-batch}(\infty ), r_j\vert \sum w_jU_j$$ 1 | s-batch ( ∞ ) , r j | ∑ w j U j problem with respect to several natural parameters. That is, we establish a classification into fixed-parameter tractable and $$\textsf{W}[1]$$ W [ 1 ] -hard problems, for parameter combinations of (i) $$\#p$$ # p = number of distinct processing times, (ii) $$\#w$$ # w = number of distinct weights, (iii) $$\#d$$ # d = number of distinct due dates, (iv) $$\#r$$ # r = number of distinct release dates. Thereby, we significantly extend the work of Hermelin et al. (Ann Oper Res 298:271–287, 2018) who analyzed the parameterized complexity of the non-batch variant of this problem without release dates. As one of our key results, we prove that $$1\vert \text {s-batch}(\infty ), r_j\vert \sum w_jU_j$$ 1 | s-batch ( ∞ ) , r j | ∑ w j U j is $$\textsf{W}[1]$$ W [ 1 ] -hard parameterized by the number of distinct processing times and distinct due dates. To the best of our knowledge, these are the first parameterized intractability results for scheduling problems with few distinct processing times. Further, we show that $$1\vert \text {s-batch}(\infty ), r_j\vert \sum w_jU_j$$ 1 | s-batch ( ∞ ) , r j | ∑ w j U j is fixed-parameter tractable parameterized by $$\#d + \#p + \#r$$ # d + # p + # r , and parameterized by $$\#d + \#w$$ # d + # w if there is just a single release date. Both results hold even if the number of jobs per batch is limited by some integer b.

AbstractThe university course timetabling problem is a challenging problem to solve. As universities have evolved, the features of this problem have changed. One emerging feature is hybrid teaching where classes can be taught online, in-person or a combination of both in-person and online. This work presents a multi-objective binary programming model that includes common university timetabling features, identified from the literature, as well as hybrid teaching features. A lexicographic solution method is outlined and computational experiments using benchmark data are used to demonstrate the key aspects of the model and explore trade-offs among the objectives considered. The results of these experiments demonstrate that the model can be used to find demand-driven schedules for universities that include hybrid teaching. They also show how the model could be used to inform practitioners who are involved in strategic decision-making at universities.

This paper concerns all-to-all network routing on regular digraphs. In previous work, we focused on efficient routing in highly symmetric digraphs with low diameter for fixed degree. Here, we show that every connected regular digraph has an all-to-all routing scheme and associated schedule with no waiting. In fact, this routing scheme becomes more efficient as the diameter goes down with respect to the degree and number of vertices. Lastly, we examine the simple scheduling algorithm called “farthest-distance-first” and prove that it yields optimal schedules for all-to-all communication in networks of interest, including Kautz graphs.

Selection hyper-heuristics are novel tools that combine low-level heuristics into robust solvers commonly used for tackling combinatorial optimization problems. However, the training cost is a drawback that hinders their applicability. In this work, we analyze the effect of training with different problem sizes to determine whether an effective simplification can be made. We select Job Shop Scheduling problems as an illustrative scenario to analyze and propose two hyper-heuristic approaches, based on Simulated Annealing (SA) and Unified Particle Swarm Optimization (UPSO), which use a defined set of simple priority dispatching rules as heuristics. Preliminary results suggest a relationship between instance size and hyper-heuristic performance. We conduct experiments training on two different instance sizes to understand such a relationship better. Our data show that hyper-heuristics trained in small-sized instances perform similarly to those trained in larger ones. However, the extent of such an effect changes depending on the approach followed. This effect was more substantial for the model powered by SA, and the resulting behavior for small and large-sized instances was very similar. Conversely, for the model powered by UPSO, data were more outspread. Even so, the phenomenon was noticeable as the median performance was similar between small and large-sized instances. In fact, through UPSO, we achieved hyper-heuristics that performed better on the training set. However, using small-sized instances seems to overspecialize, which results in spread-out testing performance. Hyper-heuristics resulting from training with small-sized instances can outperform a synthetic Oracle on large-sized testing instances in about 50% of the runs for SA and 25% for UPSO. This allows for significant time savings during the training procedure, thus representing a worthy approach.