Abstract: Abstract
This paper considers a project scheduling environment in which the activities of the project network are partitioned among a set of agents. Activity durations are controllable, i.e., every agent is allowed to shorten the duration of its activities, incurring a crashing cost. If the project makespan is reduced with respect to its normal value, a reward is offered to the agents and each agent receives a given ratio of the total reward. Agents want to maximize their profit. Assuming a complete knowledge of the agents’ parameters and of the activity network, this problem is modeled as a non-cooperative game and Nash equilibria are analyzed. We characterize Nash equilibria in terms of the existence of certain types of cuts on the project network. We show that finding one Nash equilibrium is easy, while finding a Nash strategy that minimizes the project makespan is NP-hard in the strong sense. The particular case where each activity belongs to a different agent is also studied and some polynomial-time algorithms are proposed for this case. PubDate: 2014-09-09

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: 2014-09-05

Abstract: Abstract
The Joint Replenishment Problem (
\({\hbox {JRP}}\)
) is a fundamental optimization problem in supply-chain management, concerned with optimizing the flow of goods from a supplier to retailers. Over time, in response to demands at the retailers, the supplier ships orders, via a warehouse, to the retailers. The objective is to schedule these orders to minimize the sum of ordering costs and retailers’ waiting costs. We study the approximability of
\({\hbox {JRP-D}}\)
, the version of
\({\hbox {JRP}}\)
with deadlines, where instead of waiting costs the retailers impose strict deadlines. We study the integrality gap of the standard linear-program (LP) relaxation, giving a lower bound of
\(1.207\)
, a stronger, computer-assisted lower bound of
\(1.245\)
, as well as an upper bound and approximation ratio of
\(1.574\)
. The best previous upper bound and approximation ratio was
\(1.667\)
; no lower bound was previously published. For the special case when all demand periods are of equal length, we give an upper bound of
\(1.5\)
, a lower bound of
\(1.2\)
, and show APX-hardness. PubDate: 2014-08-27

Abstract: Abstract
We consider a scheduling problem in which the criterion for assigning due dates is to make them as tight as possible, while the criterion for sequencing jobs is to minimize their tardiness. Because these two criteria conflict, we examine the trade-off between the tightness of the due dates and the tardiness of the jobs. We formulate a version of this trade-off in the case of a stochastic single-machine model with normally distributed processing times. Using lower bounds and dominance properties to curtail the enumeration, we develop a branch-and- bound procedure that is capable of solving large versions of the problem, and we report the results of computational experiments involving several hundred test problems. PubDate: 2014-08-23

Abstract: Abstract
One of the very important topics in discrete optimization, motivated by practical applications, is Internet shopping, which is becoming increasingly popular each year. More classical versions of the Internet shopping optimization problem (ISOP) are closely related to the facility location problem and some scheduling problems and have been intensively studied in the literature. In this paper, extensions of the problem are defined and studied. The issue is to buy all the necessary products for a minimum total possible price. This includes all prices of products as well as shipping costs. Studies in this paper include the ISOP with price sensitive discounts and a newly defined optimization problem: the ISOP including two different discounting functions, namely a shipping cost function as well as a price discounting function. First, these are formulated as mathematical programming problems. Then, some algorithms are constructed and extensively tested in a computational experiment. PubDate: 2014-08-17

Abstract: Abstract
An examination timetabling problem at a large American university is presented. Although there are some important differences, the solution approach is based on the ITC 2007 winning solver which is integrated in the open source university timetabling system UniTime. In this work, nine real world benchmark data sets are made publicly available and the results on four of them are presented in this paper. A new approach to further decreasing the number of student conflicts by allowing some exams to be split into multiple examination periods is also studied. PubDate: 2014-08-09

Abstract: Abstract
We consider a scheduling problem where a set of jobs has already been scheduled to minimize some cost objective on a single machine when the machine becomes unavailable for a period of time. The decision-maker needs to reschedule the jobs without excessively disrupting the original schedule. The disruption is measured as the maximum time deviation, for any given job, between the original and new schedules. We examine a general model where the maximum time disruption appears both as a constraint and as part of the cost objective. For a scheduling cost modeled as the makespan or maximum lateness, we provide a pseudopolynomial time optimal algorithm, a constant factor approximation algorithm, and a fully polynomial time approximation scheme. The approximation algorithm has an asymptotically achievable worst-case performance ratio of 2 and has average performance close to optimal. Managerial insights are given on how scheduling costs are affected by machine disruption and the approximation algorithm. PubDate: 2014-08-01

Abstract: Abstract
We study the following online problem. There are n advertisers. Each advertiser
\(a_i\)
has a total demand
\(d_i\)
and a value
\(v_i\)
for each supply unit. Supply units arrive one by one in an online fashion, and must be allocated to an agent immediately. Each unit is associated with a user, and each advertiser
\(a_i\)
is willing to accept no more than
\(f_i\)
units associated with any single user (the value
\(f_i\)
is called the frequency cap of advertiser
\(a_i\)
). The goal is to design an online allocation algorithm maximizing the total value. We first show a deterministic
\(3/4\)
-competitiveness upper bound, which holds even when all frequency caps are
\(1\)
, and all advertisers share identical values and demands. A competitive ratio approaching
\(1-1/e\)
can be achieved via a reduction to a different model considered by Goel and Mehta (WINE ‘07: Workshop on Internet and Network, Economics: 335–340, 2007). Our main contribution is analyzing two
\(3/4\)
-competitive greedy algorithms for the cases of equal values, and arbitrary valuations with equal integral demand to frequency cap ratios. Finally, we give a primal-dual algorithm which may serve as a good starting point for improving upon the ratio of
\(1-1/e\)
. PubDate: 2014-08-01

Abstract: Abstract
This paper addresses the flow shop batching and scheduling problem where sequence-dependent family setup times are present and the objective is to minimize makespan. We consider violating the group technology assumption by dividing product families into batches. In order to reduce setup times, inconsistent batches are formed on different machines, which lead to non-permutation schedules. To the best of our knowledge, this is the first time that the splitting of job families into inconsistent batches has been considered in a flow shop system. A tabu search algorithm is developed which contains several neighbourhood functions, double tabu lists and a multilevel diversification structure. Compared to the state-of-the-art meta-heuristics for this problem, the proposed tabu search algorithm achieves further improvement when the group scheduling assumption is dropped. Also, various experiments conducted on the benchmark problem instances confirm the benefits of batching. Therefore, it will be prudent for the practitioners to consider adopting inconsistent batches and non-permutation schedules to improve their operational efficiency within a reasonable amount of computational effort. PubDate: 2014-08-01

Abstract: Abstract
We consider the following list scheduling problem. We are given a set
\(S\)
of jobs which are to be scheduled sequentially on a single processor. Each job has an associated processing time which is required for its processing. Given a particular permutation of the jobs in
\(S\)
, the jobs are processed in that order with each job started as soon as possible, subject only to the following constraint: For a fixed integer
\(B \ge 2\)
, no unit time interval
\([x, x+1)\)
is allowed to intersect more than
\(B\)
jobs for any real
\(x\)
. It is not surprising that this problem is NP-hard when the value
\(B\)
is variable (which is typical of many scheduling problems). There are several real world situations for which this restriction is natural. For example, suppose in addition to our jobs being executed sequentially on a single main processor, each job also requires the use of one of
\(B\)
identical subprocessors during its execution. Each time a job is completed, the subprocessor it was using requires one unit of time in order to reset itself. In this way, it is never possible for more than
\(B\)
jobs to be worked on during any unit interval. In this paper we carry out a classical worst-case analysis for this situation. In particular, we show that any permutation of the jobs can be processed within a factor of
\(2-1/(B-1)\)
of the optimum (plus an additional small constant) when
\(B \ge 3\)
and this factor is best possible. For the case
\(B=2\)
, the situation is rather different, and in this case the corresponding factor we establish is
\(4/3\)
(plus an additional small constant), which is also best possible. It is fairly rare that best possible bounds can be obtained for the competitive ratios of list scheduling problems of this general type. PubDate: 2014-08-01

Abstract: Abstract
In this paper, we explore problems and algorithms related to the optimisation of locks, as used in inland shipping. We define several optimisation problems associated with inland shipping. We prove that the problem of scheduling a lock is NP-hard if one allows multiple ships to go through in the same lock operation. The single-ship lock optimization problem can, however, be solved in polynomial time and a novel deterministic scheduling algorithm for solving this problem is presented in this paper. PubDate: 2014-08-01

Abstract: Abstract
Closing the approximability gap between
\(3/2\)
and 2 for the minimum makespan problem on unrelated machines is one of the most important open questions in scheduling. Almost all known approximation algorithms for the problem are based on linear programs (LPs). In this paper, we identify a surprisingly simple class of instances which constitute the core difficulty for LPs: the so far hardly studied unrelated graph balancing case in which each job can be assigned to at most two machines. We prove that already for this basic setting the strongest LP-relaxation studied so far—the configuration-LP—has an integrality gap of 2, matching the best known approximation factor for the general case. This points toward an interesting direction of future research. For the objective of maximizing the minimum machine load in the unrelated graph balancing setting, we present an elegant purely combinatorial 2-approximation algorithm with only quadratic running time. Our algorithm uses a novel preprocessing routine that estimates the optimal value as good as the configuration-LP. This improves on the computationally costly LP-based algorithm by Chakrabarty et al. (Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS 2009), pp 107–116, 2009) that achieves the same approximation guarantee. PubDate: 2014-08-01

Abstract: Abstract
We study a non-preemptive strictly periodic scheduling problem. This problem arises for example in the avionic field where a set of
\(N\)
periodic tasks (measure of a sensor, data presentation, etc.) has to be scheduled on
\(P\)
processors distributed on the plane. In this article, we consider an existing heuristic which is based on the notion of equilibrium. Following a game theory analogy, each task tries successively to optimize its own schedule and, therefore, to produce the best response, given the other schedules. This iterative process continues until an equilibrium is reached. We present a new method to compute the best response which significantly improves the previously proposed heuristic, and compares favorably with MILP solutions. PubDate: 2014-07-31

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: 2014-07-26

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: 2014-07-05

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: 2014-07-05

Abstract: Abstract
In this paper, the general time hierarchical planning and scheduling approach is introduced, which integrates both detailed scheduling and due date assignment for an online problem. In this approach, time is divided into intervals of increasing size, and the different sizes form a hierarchy. We show that for a simplified model, a multiple level bin packing approach is an approximation algorithm, and we further prove that under weak assumptions, the approximation quality is bounded independently of the depth of the hierarchy. PubDate: 2014-06-19

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: 2014-06-06

Abstract: Abstract
The artificial bee colony (ABC) is a population-based metaheuristic that mimics the foraging behaviour of honeybees in order to produce high-quality solutions for optimisation problems. The ABC algorithm combines both exploration and exploitation processes. In the exploration process, the worker bees are responsible for selecting a random solution and applying it to a random neighbourhood structure, while the onlooker bees are responsible for choosing a food source based on a selection strategy. In this paper, a disruptive selection strategy is applied within the ABC algorithm in order to improve the diversity of the population and prevent premature convergence in the evolutionary process. A self-adaptive strategy for selecting neighbourhood structures is added to further enhance the local intensification capability (adaptively choosing the neighbourhood structure helps the algorithm to escape local optima). Finally, a modified ABC algorithm is hybridised with a local search algorithm, i.e. the late-acceptance hill-climbing algorithm, to quickly descend to a good-quality solution. The experiments show that the ABC algorithm with the disruptive selection strategy outperforms the original ABC algorithm. The hybridised ABC algorithm also outperforms the lone ABC algorithm when tested on examination timetabling problems. PubDate: 2014-06-01

Abstract: Abstract
We study a generalized version of the minimum makespan jobshop problem in which multiple instances of each job are to be processed. The system starts with specified inventory levels in all buffers and finishes with some desired inventory levels of the buffers at the end of the planning horizon. A schedule that minimizes the completion time of all the operations is sought. We develop a polynomial time asymptotic approximation procedure for the problem. That is, the ratio between the value of the delivered solution and the optimal one converge into one, as the multiplicity of the problem increases. Our algorithm uses the solution of the linear relaxation of a time-indexed Mixed-Integer formulation of the problem. In addition, a heuristic method inspired by this approximation algorithm is presented and is numerically shown to out-perform known methods for a large set of standard test problems of moderate job multiplicity. PubDate: 2014-04-08