Abstract: Abstract
This paper deals with “The Enchanted Journey,” which is a daily event tour booked by Bollywood-film fans. During the tour, the participants visit original sites of famous Bollywood films at various locations in Switzerland; moreover, the tour includes stops for lunch and shopping. Each day, up to five buses operate the tour. For operational reasons, however, two or more buses cannot stay at the same location simultaneously. Further operative constraints include time windows for all activities and precedence constraints between some activities. The planning problem is how to compute a feasible schedule for each bus. We implement a two-step hierarchical approach. In the first step, we minimize the total waiting time; in the second step, we minimize the total travel time of all buses. We present a basic formulation of this problem as a mixed-integer linear program. We enhance this basic formulation by symmetry-breaking constraints, which reduces the search space without loss of generality. We report on computational results obtained with the Gurobi Solver. Our numerical results show that all relevant problem instances can be solved using the basic formulation within reasonable CPU time, and that the symmetry-breaking constraints reduce that CPU time considerably. PubDate: 2014-12-01

Abstract: Abstract
This research considers the generation of random processing times for parallel machine scheduling problems. We present several processing time generation schemes that consider different levels and combinations of machine correlation and job correlation. Also, metrics to evaluate the amounts of machine relatedness and job uniformity for the randomly generated processing times of a given problem instance are presented. The proposed schemes generate desirable problem instances that can be used to test different solution approaches (such as heuristics, dynamic programming, and branch-and-bound). Computational results indicate that the schemes provide problem instances with many desirable properties. PubDate: 2014-12-01

Abstract: Abstract
This paper presents a comprehensive review on methods for real-time schedule recovery in transportation services. The survey concentrates on published research on recovery of planned schedules in the occurrence of one or several severe disruptions such as vehicle breakdowns, accidents, and delays. Only vehicle assignment and rescheduling are reviewed; crew scheduling and passenger logistics problems during disruptions are not. Real-time vehicle schedule recovery problems (RTVSRP) are classified into three classes: vehicle rescheduling, for road-based services, train-based rescheduling, and airline schedule recovery problems. For each class, a classification of the models is presented based on problem formulations and solution strategies. The paper concludes that RTVSRP is a challenging problem that requires quick and good quality solutions to very difficult and complex situations, involving several different contexts, restrictions, and objectives. The paper also identifies research gaps to be investigated in the future, stimulating research in this area. PubDate: 2014-12-01

Abstract: Abstract
The assignment of airport resources can significantly affect the quality of service provided by airlines and airports. High quality assignments can support airlines and airports in adhering to published schedules by minimising changes or delays while waiting for resources to become available. In this paper, we consider the problem of assigning available baggage sorting stations to flights which have already been scheduled and allocated to stands. A model for the problem is presented, and the different objectives which have to be considered are highlighted. A number of constructive algorithms for sorting station assignments are then presented and their effects are compared and analysed when different numbers of sorting stations are available. It can be observed that appropriate algorithm selection is highly dependent upon whether or not reductions in service time are permitted and upon the flight density in relation to the number of sorting stations. Finally, since these constructive approaches produce different solutions which are better for different trade-offs of the objectives, we utilise these as initial solutions for an evolutionary algorithm as well as for an Integer Linear Programming model in CPLEX. We show that in both cases they are helpful for improving the results which are obtainable within reasonable solution times. PubDate: 2014-12-01

Abstract: Abstract
The two-campus transport problem (TCTP) is a dial-a-ride problem with only two destinations. The problem is motivated by a transport problem between two campuses of an academic college. The two campuses are located in two different cities. Lecturers living in one city are sometimes asked to teach at the other city’s campus. The problem is that of transporting the lecturers from one campus to the other, using a known set of vehicles, so as to minimize the time the lecturers wait for their transport. We mathematically model the general TCTP, and provide an algorithm that solves it, which is polynomial in the number of lecturers. The algorithm is based on a reduction to a shortest path problem. PubDate: 2014-12-01

Abstract: Abstract
This application is motivated by a complex real-world scheduling problem found in the bottleneck workstation of the production line of an automotive safety glass manufacturing facility. The scheduling problem consists of scheduling jobs (glass parts) on a number of parallel batch processing machines (furnaces), assigning each job to a batch, and sequencing the batches on each machine. The two main objectives are to maximize the utilization of the parallel machines and to minimize the delay in the completion date of each job in relation to a required due date (specific for each job). Aside from the main objectives, the output batches should also produce a balanced workload on the parallel machines, balanced job due dates within each batch, and minimal capacity loss in the batches. The scheduling problem also considers a batch capacity constraint, sequence-dependent processing times, incompatible product families, additional resources, and machine capability. We propose a two-phase heuristic approach that combines exact methods with search heuristics. The first phase comprises a four-stage mixed-integer linear program for building the batches; the second phase is based on a Greedy Randomized Adaptive Search Procedure for sequencing the batches assigned to each machine. We conducted experiments on instances with up to 100 jobs built with real data from the manufacturing facility. The results are encouraging both in terms of computing time—5 min in average—and quality of the solutions—less than 10 % relative gap from the optimal solution in the first phase and less than 5 % in the second phase. Additional experiments were conducted on randomly generated instances of small, medium, and large size. PubDate: 2014-12-01

Abstract: Abstract
In this paper, we introduce a new kind of constraint, called a core precedence constraint, in a cyclic resource-constrained project scheduling problem (RCPSP) with precedence delays. We show, by an example, which kind of industrial constraints might be modeled by such core precedences in a periodic production setting. We then establish that these constraints can be quite easily added to an integer linear programming formulation of the cyclic RCPSP. Although core precedences seem to be very similar to classical precedence, they can induce infeasibility even without resource constraints. Moreover, we show that the feasibility checking problem is NP-complete in the strong sense, even assuming unit processing times and no resource constraints. PubDate: 2014-10-21

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

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