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: 2014-10-15

Abstract: Abstract
In this paper, we propose a metaheuristic for solving an original scheduling problem with auxiliary resources in a photolithography workshop of a semiconductor plant. The photolithography workshop is often a bottleneck, and improving scheduling decisions in this workshop can help to improve indicators of the whole plant. Two optimization criteria are separately considered: the weighted flow time (to minimize) and the number of products that are processed (to maximize). After stating the problem and giving some properties on the solution space, we show how these properties help us to efficiently solve the problem with the proposed memetic algorithm, which has been implemented and tested on large generated instances. Numerical experiments show that good solutions are obtained within a reasonable computational time. PubDate: 2014-10-02

Abstract: Numerous applications in scheduling, such as resource allocation or steel manufacturing, can be modeled using the NP-hard Independent Set problem (given an undirected graph and an integer
\(k\)
, find a set of at least
\(k\)
pairwise non-adjacent vertices). Here, one encounters special graph classes like 2-union graphs (edge-wise unions of two interval graphs) and strip graphs (edge-wise unions of an interval graph and a cluster graph), on which Independent Set remains
\(\mathrm{NP}\)
-hard but admits constant ratio approximations in polynomial time. We study the parameterized complexity of Independent Set on 2-union graphs and on subclasses like strip graphs. Our investigations significantly benefit from a new structural “compactness” parameter of interval graphs and novel problem formulations using vertex-colored interval graphs. Our main contributions are as follows:
We show a complexity dichotomy: restricted to graph classes closed under induced subgraphs and disjoint unions, Independent Set is polynomial-time solvable if both input interval graphs are cluster graphs, and is
\(\mathrm{NP}\)
-hard otherwise.
We chart the possibilities and limits of effective polynomial-time preprocessing (also known as kernelization).
We extend Halldórsson and Karlsson (2006)’s fixed-parameter algorithm for Independent Set on strip graphs parameterized by the structural parameter “maximum number of live jobs” to show that the problem (also known as Job Interval Selection) is fixed-parameter tractable with respect to the parameter
\(k\)
and generalize their algorithm from strip graphs to 2-union graphs. Preliminary experiments with random data indicate that Job Interval Selection with up to 15 jobs and
\(5\cdot 10^5\)
intervals can be solved optimally in less than 5 min. PubDate: 2014-10-02

Abstract: Abstract
In this paper, we address a parallel machine scheduling problem to minimize the total weighted completion time, where product families are involved. Major setups occur when processing jobs of different families, and sequence dependencies are also taken into account. Considering its high practical relevance, we focus on the special case where all jobs of the same family have identical processing times. In order to avoid redundant setups, batching jobs of the same family can be performed. We first develop a variable neighborhood search algorithm (VNS) to solve the interrelated subproblems in a simultaneous manner. To further reduce computing time, we also propose an iterative scheme which alternates between a specific heuristic to form batches and a VNS scheme to schedule entire batches. Computational experiments are conducted which confirm the benefits of batching. Test results also show that both simultaneous and iterative approach outperform heuristics based on a fixed batch size and list scheduling. Furthermore, the iterative procedure succeeds in balancing solution quality and computing time. PubDate: 2014-10-01

Abstract: In this paper, we propose stochastic binary quadratic programs for the scheduling resource allocation process of a wireless orthogonal frequency division multiple access network. More precisely, we formulate a two-stage stochastic model, then we further extend the two-stage model by introducing a knapsack probabilistic constrained approach, and finally we propose a multi-stage stochastic program for this problem. The models are aimed at minimizing the total power consumption of the network at each time slot of the scheduling process subject to user bit rates, sub-carrier and modulation linear constraints. In order to compute lower bounds, we derive linear and semidefinite programming relaxations for each of the proposed models. The bounds are also compared with a basic variable neighborhood search metaheuristic approach. Numerical results show tight lower bounds for the semidefinite relaxations when compared to the linear ones and with the metaheuristic. Moreover, near optimal solutions are found with the semidefinite relaxations for the two-stage model without using probabilistic constraints and for the multi-stage program as well. PubDate: 2014-10-01

Abstract: We consider a special class of large-scale, network-based, resource allocation problems under uncertainty, namely that of multi-commodity flows with time-windows under uncertainty. In this class, we focus on problems involving commodity pickup and delivery with time-windows. Our work examines methods of proactive planning, that is, robust plan generation to protect against future uncertainty. By a priori modeling uncertainties in data corresponding to service times, resource availability, supplies and demands, we generate solutions that are more robust operationally, that is, more likely to be executed or easier to repair when disrupted. We propose a novel modeling and solution framework involving a decomposition scheme that separates problems into a routing master problem and Scheduling Sub-Problems; and iterates to find the optimal solution. Uncertainty is captured in part by the master problem and in part by the Scheduling Sub-Problem. We present proof-of-concept for our approach using real data involving routing and scheduling for a large shipment carrier’s ground network, and demonstrate the improved robustness of solutions from our approach. PubDate: 2014-10-01

Abstract: The presence of uncertainties in manufacturing systems and supply chains can cause undesirable behavior. Failure to account for these in the design phase can further impair the capability of systems to respond to changes effectively. In this work, we consider a dynamic workforce-inventory control problem wherein inventory planning, production releases, and workforce hiring decisions need to be made. The objective is to develop planning rules to achieve important requirements related to dynamic transient behavior when system parameters are imprecisely known. To this end, we propose a resilience optimization model for the problem and develop a novel local search procedure that combines the strengths of recent developments in robust optimization technology and small signal stability analysis of dynamic systems. A numerical case study of the problem demonstrates significant improvements of the proposed solution in controlling fluctuations and high variability found in the system’s inventory, work-in-process, and workforce levels. Overall, the proposed model is shown to be computationally efficient and effective in hedging against model uncertainties. PubDate: 2014-10-01

Abstract: In the 1970’s John Gittins discovered that multi-armed bandits, an important class of models for the dynamic allocation of a single key resource among a set of competing projects, have optimal solutions of index form. At each decision epoch such policies allocate the resource to whichever project has the largest Gittins index. Since the 1970’s, Gittins’ index result together with a range of developments and reformulations of it have constituted an influential stream of ideas and results contributing to research into the scheduling of stochastic objects. We give a brief account of many of the most important contributions to this work and proceed to describe how index theory has recently been developed to produce strongly performing heuristic policies for the dynamic allocation of a divisible resource to a collection of stochastic projects (or bandits). A limitation on this work concerns the need for the structural requirement of indexability which is notoriously difficult to establish. We introduce a general framework for the development of index policies for dynamic resource allocation which circumvents this difficulty. We utilise this framework to generate index policies for two model classes of independent interest. Their performance is evaluated in an extensive numerical study. PubDate: 2014-10-01

Abstract: In addition to having to handle constantly increasing numbers of aircraft, modern airports also have to address a wide range of environmental regulations and requirements. As airports work closer and closer to their maximal possible capacity, the operations problems that need to be solved become more and more complex. This increasing level of complexity leads to a situation where the introduction of advanced decision support systems becomes more and more attractive. Such systems have the potential to improve efficient airside operations and to mitigate against the environmental impact of those operations. This paper addresses the problem of moving aircraft from one location within an airport to another as efficiently as possible in terms of time and fuel spent. The problem is often called the ground movement problem and the movements are usually from gate/stands to a runway or vice-versa. We introduce a new sequential graph based algorithm to address this problem. This approach has several advantages over previous approaches. It increases the realism of the modelling and it draws upon a recent methodology to more accurately estimate taxi times. The algorithm aims to absorb as much waiting time for delay as possible at the stand (with engines off) rather than out on the taxiways (with engines running). The impact of successfully achieving this aim is to reduce the environmental pollution. This approach has been tested using data from a European hub airport and it has demonstrated very promising results. We compare the performance of the algorithm against a lower bound on the taxi time and the limits to the amount of waiting time that can be absorbed at stand. PubDate: 2014-10-01

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