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
In this paper, a single-machine scheduling problem with periodic maintenance and non-preemptive jobs is considered. The objective is to minimize the makespan. It shows that the classical list scheduling (LS) algorithm, the longest processing time first (LPT) algorithm, and the modified longest processing time first (MLPT) algorithm all have the same worst-case ratio and the same computational complexity for the considered problem. To compare the performances of three considered algorithms in detail, the worst-case ratios of algorithms are formed as single-variable functions of the total number of maintenance activities needed in the optimal schedule. Analysis results show that the bound associated with the LS algorithm is always dominated by the bound associated with the LPT algorithm, and the latter is always dominated by the bound associated with the MLPT algorithm. PubDate: 2014-06-01

Abstract: Abstract
This paper studies an online scheduling problem with immediate and reliable lead-time quotation. A manufacturer either accepts an order by quoting a reliable lead-time on its arrival or rejects it immediately. The objective is to maximize the total revenue of completed orders. Keskinocak et al. (Management Science 47(2):264–279, 2001) studied a linear revenue function in a discrete model with integer release time of order, and proposed a competitive strategy Q-FRAC. This paper investigates a relaxed revenue function in both discrete and continuous models where orders are released at integer and real time points, respectively. For the discrete model, we present a revised Q-FRAC strategy that is optimal in competitiveness for concave and linear revenue functions with unit length and uniform weight of order, improving the previous results in Keskinocak et al. (Management Science 47(2):264–279, 2001). For the scenario with uniform length
$p$
and nonuniform weight of order, we prove an optimal strategy for the case with
$p=1$
and the nonexistence of competitive strategies for the case with
$p>1$
. For the continuous model, we present an optimal strategy in competitiveness for the case with uniform weight of order and linear revenue functions, and prove the nonexistence of competitive strategies for the other case with nonuniform weight of order. PubDate: 2014-06-01

Abstract: Abstract
The Resource Constrained Project Scheduling Problem is one of the most intensively investigated scheduling problems. It requires scheduling a set of interrelated activities, while considering precedence relationships, and limited renewable resources allocation. The objective is to minimize the project duration. We propose a new destructive lower bound for this challenging
${\mathcal {NP}}$
-hard problem. Starting from a previously suggested LP model, we propose several original valid inequalities that aim at tightening the model representation. These new inequalities are based on precedence constraints, incompatible activity subsets, and nonpreemption constraints. We present the results of an extensive computational study that was carried out on 2,040 benchmark instances of PSPLIB, with up to 120 activities, and that provide strong evidence that the new proposed lower bound exhibits an excellent performance. In particular, we report the improvement of the best known lower bounds of 5 instances. PubDate: 2014-06-01

Abstract: Abstract
We present an Iterated Local Search (ILS) algorithm for solving the single-machine scheduling problem with sequence-dependent setup times to minimize the total weighted tardiness. The proposed ILS algorithm exhibits several distinguishing features, including a new neighborhood structure called Block Move and a fast incremental evaluation technique, for evaluating neighborhood solutions. Applying the proposed algorithm to solve 120 public benchmark instances widely used in the literature, we achieve highly competitive results compared with a recently proposed exact algorithm and five sets of best solutions of state-of-the-art metaheuristic algorithms in the literature. Specifically, ILS obtains the optimal solutions for 113 instances within a reasonable time, and it outperforms the previous best-known results obtained by metaheuristic algorithms for 34 instances and matches the best results for 82 instances. In addition, ILS is able to obtain the optimal solutions for the remaining seven instances under a relaxed time limit, and its computational efficiency is comparable with the state-of-the-art exact algorithm by Tanaka and Araki (Comput Oper Res 40:344–352, 2013). Finally, on analyzing some important features that affect the performance of ILS, we ascertain the significance of the proposed Block Move neighborhood and the fast incremental evaluation technique. 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