Abstract: Abstract
We show that the following fundamental question in student sectioning can be efficiently decided in polynomial time: Is it possible to assign
\(m\)
students to
\(k\)
sectioned courses with respect to a given timetable with
\(l\)
timeslots such that the individual capacities of all sections are not exceeded and no student has more than one appointment per timeslot? Our result opens the possibility of efficiently checking the feasibility of candidate timetables with respect to this question as part of timetabling algorithms. Based on a succinct representation of solutions, we also provide an algorithm to compute optimal assignments in
\(O( k^2l^2 \log (\mathrm{sum}_{A}))\)
, where
\(\mathrm{sum}_{A}\)
is the sum of all specified section capacities. On the other hand, we prove that adding any single of the following constraints turns the above question into an NP-complete problem:
Course-selection constraint: Student’s course-selections must be respected.
Timeslot constraint: Students have individual timeslot restrictions.
Multiple-event constraint: Sections may have multiple events in the timetable, and there must be no timeslot clashes between all section-events for each student.
Hence our investigation gives insight into the location of the borderline between efficiently solvable and computationally hard problem variations. PubDate: 2015-04-11

Abstract: Abstract
Single-machine weighted earliness tardiness scheduling is a prevalent problem in just-in-time production environments. Yet, the case with distinct due dates is strongly NP-hard. Herein, it is approximately solved using ASV, an ant colony-based system with a reduced number of ants and of colonies and with daemon actions that explore the search space around the ants using a variable neighborhood search (VNS). The numerical investigation provides computational proof of the utility of the daemon actions. In addition, it infers that these latter can be applied either to the initial or to subsequent colonies. Furthermore, it highlights the importance of using ant colony optimization as the multiple restart engine of VNS. Finally, it shows that ASV obtains the optimum for most small-sized instances. It has a 0.2 % average deviation from the optimum over all benchmark instances. PubDate: 2015-04-08

Abstract: Abstract
We study a scheduling problem in which jobs may be split into parts, where the parts of a split job may be processed simultaneously on more than one machine. Each part of a job requires a setup time, however, on the machine where the job part is processed. During setup, a machine cannot process or set up any other job. We concentrate on the basic case in which setup times are job-, machine- and sequence-independent. Problems of this kind were encountered when modelling practical problems in planning disaster relief operations. Our main algorithmic result is a polynomial-time algorithm for minimising total completion time on two parallel identical machines. We argue, why the same problem with three machines is not an easy extension of the two-machine case, leaving the complexity of this case as a tantalising open problem. We give a constant-factor approximation algorithm for the general case with any number of machines and a polynomial-time approximation scheme for a fixed number of machines. For the version with the objective to minimise total weighted completion time, we prove NP-hardness. Finally, we conclude with an overview of the state of the art for other split scheduling problems with job-, machine- and sequence-independent setup times. PubDate: 2015-04-01

Abstract: Abstract
An event in a schedule is a job start, interruption, resumption or completion time. A shift in a schedule is an non-idling interval between two events that does not contain other events. If a scheduling problem with a regular criterion has only integer data (and we consider here only such problems), then the length of smallest shifts required in optimal nonpreemptive schedules is obviously 1. The length of smallest shifts required in optimal preemptive schedules, however, can be infinitely small. As Sauer and Stone (Order 4:195–206, 1987) showed more than 25 years ago, shifts of length less than
\(m^{-n}\)
are not required in shortest preemptive schedules of
\(n\)
unit-length jobs with precedence constraints on
\(m\)
identical parallel machines. They showed, on the other hand, that there are instances for infinitely many
\(n\)
such that shifts of length less than
\((m-1)^{-n/(3m)}(m-2)/m\)
can be required if
\(m\ge 3\)
. In this paper, we continue research in the same direction and strengthen their results, finding the respective tighter bounds,
\(m^{-(n+1)/2}\)
and
\((m-1)^{-n/(m+3)}\)
. We also obtain similar results for other preemptive scheduling problems on identical parallel machines. A useful consequence of certain of these results is that preemptive scheduling problems with unequal release dates and/or unequal due dates can require even smaller shifts for optimality. We also identify problems whose optimal preemptive schedules do not require shifts of length less than
\(1/m\)
. PubDate: 2015-04-01

Abstract: Abstract
One of the basic and fundamental scheduling problems is to minimize the machine completion time vector in the
\(\ell _p\)
norm, a direct extension of the well-studied objective makespan (
\(l_{\infty }\)
norm), on parallel machines. We concentrate on the on-line and preemptive version of this problem where jobs arrive one by one over a list to be allocated to two uniform machines with job preemption permitted. We present a best possible deterministic on-line scheduling algorithm for this problem along with a matching lower bound, generalizing existing results for the identical machines scheduling problem in the literature. One notable feature of this work is the highly involved technicality compared to similar analysis in the existing literature, mainly due to the intrinsic unavailability of a closed-form formula for the competitive ratio. PubDate: 2015-04-01

Abstract: Abstract
This paper addresses a multi-activity multi-day shift scheduling problem in a continuous and flexible environment including a heterogeneous workforce. Given days-off schedules associated with each employee, our objective is to construct and assign admissible multi-activity shifts to employees on their work days in a way that minimizes under-staffing and over-staffing with a restricted budget on workforce cost. A hybrid heuristic which combines tabu search with a branch-and-bound procedure is proposed to solve the problem. The computational experiments prove that our method provides good schedules in relatively short computing times. PubDate: 2015-04-01

Abstract: Abstract
Scheduling in semiconductor manufacturing is of vital importance due to the impact on production performance indicators such as equipment utilization, cycle time, and delivery times. With the increasing complexity of semiconductor manufacturing, ever-new products and demanding customers, scheduling plans for efficient production control become crucial. Scheduling and control are mutually dependent as control requires information from scheduling, for example, where jobs are processed, and scheduling requires control information, for example, on which equipment operations can be processed. Based on a survey of the literature, this article proposes a review and an outlook for the potential improvements by binding scheduling decisions and information coming from advanced process control systems in semiconductor manufacturing. PubDate: 2015-04-01

Abstract: Abstract
We consider two-agent scheduling on a single machine with release dates and preemption to minimize the maximum lateness. In this scheduling model, there are two agents
\(A\hbox { and }B\)
each having his own job set
\(\mathcal{J}_A= \{ J^a_1, \ldots , J^a_{n_a}\}\hbox { and }\mathcal{J}_B= \{ J^b_1, \ldots , J^b_{n_b}\}\)
, respectively. Each job
\(J_j\in \mathcal{J}_A\cup \mathcal{J}_B\)
has a release date
\(r_j\)
and the
\(n=n_a+n_b\)
jobs need to be preemptively scheduled on a single machine. Leung et al. (Oper Res 58:458–469, 2010) present a comprehensive study of two-agent scheduling in various machine environments. They show that problem
\(1 r_j,\; \text{ pmtn } L^a_{\max }: f^b_{\max }\le Q\)
can be solved in
\(O(n_a\log n_a+ n_b\log n_b)\)
time. They use the strategy that schedules the jobs of agent
\(B\)
without preemption as late as possible under the restriction
\(f^b_{\max }\le Q\)
. We show that the strategy fails to work even when
\(n_a=n_b=1\)
, invalidating their result. We then study the minimization problem
\(1 r_j,\; \text{ pmtn } L^a_{\max }: f^b_{\max }\le Q\)
and the Pareto optimization problem
\(1 r_j,\; \text{ pmtn } (L^a_{\max }: L^b_{\max })\)
. We show that the two problems can be solved in
\(O(n_an \log n)\hbox { and }O(n_an_bn \log n)\)
time, respectively. PubDate: 2015-04-01

Abstract: Abstract
In this paper, we present a new scheduling problem and describe a shortest path-based heuristic as well as a dynamic programming-based exact optimization algorithm to solve it. The selective multi-category parallel-servicing problem arises when a set of jobs has to be scheduled on a server (machine) with limited capacity. Each job requests service in a prespecified time window and belongs to a certain category. Jobs may be serviced partially, incurring a penalty; however, only jobs of the same category can be processed simultaneously. One must identify the best subset of jobs to process in each time interval of a given planning horizon, while respecting the server capacity and scheduling requirements. We compare the proposed solution methods with a Mixed Integer Linear Programming (MILP) formulation and show that the dynamic programming approach is faster when the number of categories is large, whereas the MILP can be solved faster when the number of categories is small. PubDate: 2015-04-01

Abstract: Abstract
In this paper, a scheduling problem is considered which arises in the packaging industry. Plastic and foil wrappers used for packaging candy bars, crisps and other snacks typically require overlay printing with multiple colours. Printing machines used for this purpose usually accommodate a small number of colours which are loaded into a magazine simultaneously. If two consecutively scheduled print jobs require significantly different colour overlays, then substantial down times are incurred during the transition from the former magazine colour configuration to the latter, because ink cartridges corresponding to colours not required for the latter job have to be cleaned after completion of the former job. The durations of these down times are therefore sequence dependent (the washing and refilling time is a function of the number of colours in which two consecutive printing jobs differ). It is consequently desirable to schedule print jobs so that the accumulated down times associated with all magazine colour transitions are as short as possible for each printing machine. We show that an instance of this scheduling problem can be modelled as the well-known tool switching problem, which is tractable for small instances only. The problem can, however, be solved rather effectively in heuristic fashion by decomposing it into two subproblems: a job grouping problem (which can be modelled as a unicost set covering problem) and a group sequencing problem (which is a generalisation of the celebrated travelling salesman problem). We solve the colour print scheduling problem both exactly and heuristically for small, randomly generated test problem instances, studying the trade-off between the time efficiency and solution quality of the two approaches. Finally, we apply both solution approaches to real problem data obtained from a printing company in the South African Western Cape as a special case study. PubDate: 2015-04-01

Abstract: Abstract
Many supply chains use returnable packaging such as plastic and metal containers, folding boxes, racks, and trays to transport components from suppliers to buyers. This study investigates the scheduling problem of a supplier that produces jobs for several buyers where the jobs for each buyer have to be delivered in that buyer’s returnable containers. Empty containers are provided by the buyers at certain release dates. The supplier can process a job when no adequate empty containers are available, but then incurs extra handling costs to pack the job into auxiliary packaging and repack it later. This study extends single machine scheduling with weighted earliness and tardiness penalties and batching by including returnable containers and repacking penalties. A mathematical programming formulation and a two-stage heuristic for this previously unstudied NP-hard scheduling problem are proposed and evaluated in a numerical study. PubDate: 2015-03-25

Abstract: Abstract
In this paper we study differences between contiguous and non-contiguous parallel task schedules. Parallel tasks can be executed on more than one processor simultaneously. In the contiguous schedules, indices of the processors assigned to a task must be a sequence of consecutive numbers. In the non-contiguous schedules, processor indices may be arbitrary. Optimum non-preemptive schedules are considered. Given a parallel task instance, the optimum contiguous and non-contiguous schedules can be of different lengths. We analyze minimal instances where such a difference may arise, provide bounds on the difference of the two schedules lengths, and prove that deciding whether the difference in schedule length exists is NP-complete. PubDate: 2015-03-24

Abstract: Abstract
The purpose of this research is to develop a new procedure for generating a proactive baseline schedule for the resource-constrained project scheduling problem. The main advantage of this new procedure is that it is completely independent of the reactive policy applied. This contrasts with the traditional methods that assume a predefined reactive policy. First, we define a new robustness measure, then we introduce a branch-and-cut method for solving a sample average approximation of our original problem. In a computational experiment, we show that our procedure outperforms two other published methods, assuming different robustness measures. PubDate: 2015-03-13

Abstract: Abstract
The resource-constrained project scheduling problem with minimum and maximum time lags (RCPSP/max) is a general model for resource scheduling in many real-world problems (such as manufacturing and construction engineering). We consider RCPSP/max problems where the durations of activities are stochastic and resources can have unforeseen breakdowns. Given a level of allowable risk,
\(\alpha \)
, our mechanisms aim to compute the minimum robust makespan execution strategy. Robust makespan for an execution strategy is any makespan value that has a risk less than
\(\alpha \)
. The risk for a makespan value,
\(M\)
given an execution strategy, is the probability that a schedule instantiated from the execution strategy will not finish before
\(M\)
given the uncertainty over durations and resources. We make three key contributions: (a) firstly, we provide an analytical evaluation of resource breakdowns and repairs on executions of activities; (b) we then incorporate such information into a local search framework and generate execution strategies that can absorb resource and durational uncertainties; and (c) finally, to improve robustness of resulting strategies, we propose resource breakdown aware chaining procedure with three different metrics. This chaining procedure computes resource allocations by predicting the effect of breakdowns on robustness of generated strategies. Experiments show effectiveness of our proposed methods in providing more robust execution strategies under uncertainty. PubDate: 2015-03-12

Abstract: Abstract
The resource-constrained project scheduling problem (RCPSP) has been widely studied. A fundamental assumption of the basic type of RCPSP is that activity durations are deterministic (i.e., they are known in advance). In reality, however, this is almost never the case. In this article, we illustrate why it is important to incorporate activity duration uncertainty, and develop an exact procedure to optimally solve the stochastic resource-constrained scheduling problem. A computational experiment shows that our approach works best when solving small- to medium-sized problem instances where activity durations have a moderate-to-high level of variability. For this setting, our model outperforms the existing state-of-the-art. In addition, we use our model to assess the optimality gap of existing heuristic approaches, and investigate the impact of making scheduling decisions also during the execution of an activity rather than only at the end of an activity. PubDate: 2015-03-10

Abstract: Abstract
Makespan minimization on a set of parallel machines is one of the most widely studied problems in scheduling theory. A new result is presented which improves on the classical Coffman–Sethi a posteriori bound on the relative error of the LPT algorithm. It is shown that the ratio of these two bounds (the old one to the new one) can be arbitrarily large. PubDate: 2015-02-11

Abstract: Abstract
In this paper, we study a robust single-machine scheduling problem under four alternative optimization criteria: minimizing total completion time, minimizing total weighted completion time, minimizing maximum lateness, and minimizing the number of late jobs. We assume that job processing times are subject to uncertainty. Accordingly, we construct three alternative uncertainty sets, each of which defines job processing times that can simultaneously occur. The robust optimization framework assumes that, given a job schedule, a worst-case set of processing times will be realized from among those allowed by the uncertainty set under consideration. For each combination of objective function and uncertainty set, we first analyze the problem of identifying a set of worst-case processing times with respect to a fixed schedule, and then investigate the problem of selecting a schedule whose worst-case objective is minimal. PubDate: 2015-02-06

Abstract: Abstract
In this paper, we consider a single-machine scheduling problem (P) inspired from manufacturing instances. A release date, a deadline, and a regular (i.e., non-decreasing) cost function are associated with each job. The problem takes into account sequence-dependent setup times and setup costs between jobs of different families. Moreover, the company has the possibility to reject some jobs/orders, in which case a penalty (abandon cost) is incurred. Therefore, the problem at hand can be viewed as an order acceptance and scheduling problem. Order acceptance problems have gained interest among the research community over the last decades, particularly in a make-to-order environment. We propose and compare a constructive heuristic, local search methods, and population-based algorithms. Tests are performed on realistic instances and show that the developed metaheuristics significantly outperform the currently available resolution methods for the same problem. PubDate: 2015-02-01