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
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
There are many situations when, due to unexpected delays, the supplier may not be able to deliver some orders by the promised due dates. We present a model for quoting attainable delivery times to minimize tardiness penalties and delivery costs, when deliveries take place in batches. We show that the general problem is strongly
\({\mathcal {NP}}\)
-hard, but when all orders have the same per-unit due-date-assignment cost, it is
\({\mathcal {NP}}\)
-hard only in the ordinary sense. For the latter case, we present a pseudo-polynomial algorithm, which is converted into a fully polynomial-time approximation scheme. If the tardiness penalties are also identical, we show that the problem can be solved in polynomial time. PubDate: 2015-02-01

Abstract: Abstract
In this paper, we initiate the study of minimizing power consumption in the broadcast scheduling model. In this setting, there is a wireless transmitter. Over time requests arrive at the transmitter for pages of information. Multiple requests may be for the same page. When a page is transmitted, all requests for that page receive the transmission simultaneously. The speed the transmitter sends data at can be dynamically scaled to conserve energy. We consider the problem of minimizing flow time plus energy, the most popular scheduling metric considered in the standard online scheduling model when the scheduler is energy aware. We will assume that the power consumed is modeled by an arbitrary convex function. For this problem, there is an
\(\Omega (n)\)
lower bound on the competitive ratio. Due to the lower bound, we consider using resource augmentation and give a scalable algorithm. PubDate: 2015-02-01

Abstract: Abstract
This paper introduces a shift rostering problem that surprisingly has not been studied in the literature: the weekend shift rostering problem. It is motivated by our experience that employees’ shift preferences predominantly focus on the weekends, since many social activities happen during weekends. The weekend rostering problem (WRP) addresses the rostering of weekend shifts, for which we design a problem-specific heuristic. We consider the WRP as the first phase of the shift rostering problem. To complete the shift roster, the second phase assigns the weekday shifts. This decomposition reflects how shift rosters are often created manually in practice, which makes the decomposition method proposed in this paper a more intuitive approach for business users compared to approaches without this decomposition. We believe that such approaches enable business users to effectively analyze and steer the outcomes of algorithms for shift rostering especially on criteria that are relevant to them such as those concerning weekends. We analyze and discuss effects of this two-phase approach both on the weekend shift roster and on the roster as a whole. We demonstrate that our first-phase weekend rostering heuristic is effective both on generated instances and real-life instances. For situations where the weekend shift roster is one of the key determinants of the quality of the complete roster, our two-phase approach is shown to be effective. PubDate: 2015-02-01

Abstract: Abstract
We study a set of scheduling problems on a uniform machine setting. We focus on the case of equal processing time jobs with the additional feature of job rejection. Jobs can either be processed on a predefined set of machines or rejected. Rejected jobs incur a rejection penalty and have no effect on the scheduling criterion under consideration. A solution to our problems consists of partitioning the jobs into two subsets,
\(A\)
and
\(\overline{A}\)
, which are the set of accepted and the set of rejected jobs, respectively. In addition, jobs in set
\(A\)
have to be scheduled on the
\(m\)
machines. We evaluate the quality of a solution by two criteria. The first,
\(F_{1}\)
, can be any regular scheduling criterion, while the latter,
\(F_{2}\)
, is the total rejection cost. We consider two possible types of regular scheduling criteria; the former is a maximization criterion, while the latter is a summation criterion. For each criterion type we consider four different problem variations. We prove that all four variations are solvable in polynomial time for
\(any\)
maximization type of a regular scheduling criterion. When the scheduling criterion is of summation type, we show that only one of the four problem variations is solvable in polynomial time. We provide a pseudo-polynomial time algorithms to solve interesting variants of the
\(\mathcal {NP}\)
-hard problems, as well as a polynomial time algorithm that solves various other special cases. PubDate: 2015-02-01

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