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
Upon graduation from medical school, medical students join residency programs to complete their clinical training and fulfill specialty board certification requirements. During residency, they are assigned several years of clinical rotations, where they work under the supervision of physician faculty in a variety of different settings, to ensure that they gain the requisite training prior to beginning independent practice. These rotations typically last a short period of time, and the problem of determining a schedule for all the residents in a program can be quite tedious. In this paper, a basic residency scheduling problem that produces a 1-year schedule is defined, and a proof of NP-completeness is presented. Furthermore, a specific model of the residency scheduling program for the internal medicine residency program at the University of Illinois College of Medicine at Urbana-Champaign is studied. Finally, a method for determining alternate optima is presented. PubDate: 2014-06-01

Abstract: Abstract
The berth allocation problem (BAP), which defines a processing interval and a berth at the quay wall for each ship to be (un-)loaded, is an essential decision problem for efficiently operating a container port. In this paper, we integrate mobile quay walls into the BAP. Mobile quay walls are huge propelled floating platforms, which encase ships moored at the immobile quay and provide additional quay cranes for accelerating container processing. Furthermore, additional ships can be processed at the seaside of the platform, so that scarce berthing space at a terminal is enlarged. We formalize the BAP with mobile quay walls and provide suitable solution procedures. PubDate: 2014-06-01

Abstract: Abstract
We study mechanism design for a single-server setting where jobs require compensation for waiting, while waiting cost is private information to the jobs. With given priors on the private information of jobs, we aim to find a Bayes–Nash incentive compatible mechanism that minimizes the total expected payments to the jobs. Following earlier work in the auction literature, we show that this problem is solved, in polynomial time, by a version of Smith’s rule. When both waiting cost and processing times are private, we show that optimal mechanisms generally do not satisfy an independence condition known as IIA, and conclude that a closed form for optimal mechanisms is generally not conceivable. PubDate: 2014-04-18

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-04-16

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

Abstract: Abstract
We study practical scheduling problems with a major decision referring to the number of machines to be used. We focus on a two-stage flexible flowshop, where each job is processed on the first (critical) machine, and then continues to one of the second-stage parallel machines. Jobs are assumed to have identical processing times, and are processed in batches. A setup time is required when starting a new batch. We consider two objective functions: minimum makespan and minimum flowtime. In both cases, a closed form expression for the optimal number of machines to be used is introduced, and a unique and unusual sequence of decreasing batch sizes is shown to be optimal. PubDate: 2014-04-01

Abstract: Abstract
The multi-activity multi-task shift scheduling problem requires the assignment of interruptible activities and uninterruptible tasks to a set of employees in order to satisfy a demand function. In this paper, we consider the personalized variant of the problem where the employees have different qualifications, preferences, and availabilities. We present a branch-and-price algorithm to solve this problem. The pricing subproblems in column generation are formulated with context-free grammars that are able to model complex rules in the construction of feasible shifts for an employee. We present results for a large set of instances inspired by real cases and show that this approach is sufficiently flexible to handle different classes of problems. PubDate: 2014-04-01

Abstract: Abstract
Resource leveling problems arise whenever it is expedient to reduce the fluctuations in resource utilization over time, while maintaining a prescribed project completion deadline. Several resource leveling objective functions may be defined, consideration of which results in well-balanced resource profiles. In this paper, we concentrate on a special objective function that determines the costs arising from increasing or decreasing the resource utilizations. The resulting total adjustment cost problem occurs, for example, in the construction industry and can be formulated using mixed-integer linear programming models. Apart from a discrete time-based formulation, two polynomial formulations, namely an event-based model and a start-based model, which exploit structural properties of the problem are presented. In addition, a heuristic solution algorithm is proposed to generate start solutions for the problem. We use CPLEX 12.4 to solve medium-scale instances known from the literature. A computational performance analysis shows that the discrete time-based model and the start-based model are suitable for practical applications. PubDate: 2014-04-01

Abstract: Abstract
In the past two decades, scheduling with machine availability constraints has received considerable attention. Until recently most research has focused on the setting where all machine unavailability information is known at the beginning of the scheduling horizon. In reality, this is not practical in some cases. The machine may become unavailable to process jobs due to a machine breakdown or an occurrence of an emergent job that has to be processed immediately. In both cases, the start time of the unavailable interval is unknown beforehand, and the length of the interval may not be known until the end of the interval. In this article, we consider the situation in which the scheduler has to make scheduling decisions without any knowledge of the machine unavailable intervals. Of particular interest is the problem of minimizing total weighted completion time. When there are two or more unavailable intervals on a single machine, Fu et al. (2009) have shown that the problem is exponentially inapproximable even when jobs’ weights are equal to their processing times and one has full knowledge of unavailability. So in this paper we consider the scheduling problem on a single machine with a single unavailable period. And, we assume that every job has a weight proportional to its processing time. Based on whether the unavailable interval is due to a breakdown or an emergent job, we have the breakdown model and the emergent job model. First we show that no
$\tfrac{\sqrt{5}+1}{2}$
-competitive online algorithm exists for the breakdown model, and no
$\tfrac{11-\sqrt{2}}{7}$
-competitive online algorithm exists for the emergent job model. Next, we show that the simple LPT rule can give a 2- and a
$\tfrac{9}{5}$
-competitive ratio for the breakdown model and the emergent job model, respectively. Further, we show that the ratios are tight by examples. For the offline case, we show that the First Fit LPT (FF-LPT) rule can give a tight approximation ratio of 2 and 4/3 for the breakdown model and the emergent job model, respectively. Finally, our experimental results show that, in practice, both LPT and FF-LPT perform very well and the performance improves when the number of jobs
$n$
increases. In both models, when
$n \ge 50$
, the worst case error ratio is much better than the theoretical bounds. PubDate: 2014-04-01

Abstract: Abstract
We consider online preemptive scheduling problems where jobs have deadlines and the objective is to maximize the total weight of jobs completed before their deadlines. In the first problem, preemptions are not free but incur a penalty. In the second problem, a job has to be accepted or rejected immediately upon arrival, and may need to be immediately allocated a fixed scheduling interval as well; if these accepted jobs are not eventually completed, the job is lost, and a penalty is incurred. We give an algorithm with the optimal competitive ratio for the first problem, and new and improved algorithms for the second problem, under different models of preemptions and job weights. PubDate: 2014-04-01

Abstract: Abstract
In this paper we discuss exact and approximation algorithms for scheduling a single machine with additional non-renewable resource constraints. Given the initial stock levels of some non-renewable resources (e.g., raw materials, fuel, money), and time points along with replenishment quantities, a set of resource consuming jobs has to be scheduled on the machine such that there are enough resources for starting each job, and the makespan is minimized. We show that the problem admits a pseudo-polynomial time algorithm when the number of replenishments is not part of the input, and also present an FPTAS when there is only a single resource, and it is replenished only once. We also describe a PTAS for the problem with a constant number of replenishments. PubDate: 2014-04-01

Abstract: Abstract
This paper presents a new model and solution methodology for the problem faced by companies that provide rehabilitative services to clinic and home-bound patients. Given a set of multi-skilled therapists and a group of geographically dispersed patients, the objective is to construct weekly tours for the therapists that minimize the travel, treatment, and administrative costs while ensuring that all patients are seen within their time windows and that a host of labor laws and contractual agreements are observed. The problem is complicated by three factors that prevent a daily decomposition: (i) overtime rates kick in only after 40 regular hours are worked during the week, (ii) new patients must be seen by a licensed therapist on their first visit, and (iii) for some patients only the frequency and not the actual days on which they are to be seen is specified. The problem is formulated as a mixed-integer linear program but after repeated attempts to solve small instances with commercial software failed, we developed an adaptive sequential greedy randomized adaptive search procedure. The phase I logic of the procedure builds one daily schedule at a time for each therapist until all patients are routed. In phase II, several neighborhoods are explored to arrive at a local optimum. Extensive testing with both real data provided by a U.S. rehab company and datasets derived from them demonstrated the value of the purposed procedure with respect to current practice. The results indicated that cost reductions averaging over 18.09 % are possible. PubDate: 2014-04-01

Abstract: Abstract
The resource availability cost problem (RACP) (Möhring, Operations Research, 32:89–120, 1984) is commonly encountered in project scheduling. RACP aims to minimize the resource availability cost of a project by a given project deadline. In this study, RACP is extended from a single mode to a multi-mode called multi-mode RACP (MMRACP), which is more complicated than RACP but more convenient in practice. To solve MMRACP efficiently, forward activity list (FAL), a schedule generation scheme, is proposed. Heuristic algorithms are designed according to the characteristics of FAL to repair infeasible solutions and to improve the fitness of the solution. Modified particle swarm optimization (MPSO), which combines the advantages of particle swarm optimization and scatter search, is proposed to make the search for the best solution efficient. Computational experiments involving 180 instances are performed to validate the performance of the proposed algorithm. The results reveal that MPSO using FAL is a very effective method to solve MMRACP. PubDate: 2014-03-26