An iterated greedy metaheuristic for the blocking job shop scheduling problem

In this paper we consider a job shop scheduling problem with blocking (BJSS) constraints. Blocking constraints model the absence of buffers (zero buffer), whereas in the traditional job shop scheduling model buffers have infinite capacity. There are two known variants of this problem, namely the blocking job shop scheduling with swap allowed (BWS) and the one with no swap allowed (BNS). This scheduling problem is receiving an increasing interest in the recent literature, and we propose an Iterated Greedy (IG) algorithm to solve both variants of the problem. IG is a metaheuristic based on the repetition of a destruction phase, which removes part of the solution, and a construction phase, in which a new solution is obtained by applying an underlying greedy algorithm starting from the partial solution. A comparison with recent published results shows that the iterated greedy algorithm outperforms other state-of-the-art algorithms on benchmark instances. Moreover it is conceptually easy to implement and has a broad applicability to other constrained scheduling problems.     

Optimal preventive maintenance scheduling of thermal generating units in power systems —A survey of problem formulations and solution methods

Preventive maintenance scheduling of thermal generating units occupies a significant place in power system operation and expansion planning; at the same time it is a challenging optimization problem. The purpose of this paper is to analyse essential features of the maintenance scheduling problem, including imposed constraints and various objectives, as well as to present the results of the research work done in this field using operational research methods. Papers published during last fifteen years are discussed, with special regard for the applied optimization techniques.     

Designing Conferences to Improve Resource Utilization and Participant Satisfaction

We look at a conference scheduling problem with the objective of maximizing the ability of participants to attend sessions of interest. This problem was addressed in an article by Eglese and Rand; conference scheduling has otherwise received little attention in management science literature. Related problems of class- and exam-scheduling have been extensively studied and published, yet few cases consider participant (e.g. student) preferences. Our formulation, which a variation of that used by Eglese and Rand, includes prioritized preferences for conference sessions, as well as schedule resource constraints. The purpose of this paper is to extend the previous work by exploring the impact of various scheduling decisions on participant satisfaction (measured by enrollment in desired sessions). We use a previously published algorithm to look at issues such as conference length and make general observations that may aid the conference-scheduling decision maker.     

Solving a chemical batch scheduling problem by local search

In this paper the following chemical batch scheduling problem is considered: a set of orders has to be processed on a set of facilities. For each order a given amount of a product must be produced by means of chemical reactions before a given deadline. The production consists of a sequence of processes whereby each process has to be performed by one facility out of a given subset of facilities allowed for this process. The processing times depend on the choice of the facility and the processing is done in batch mode with given minimum and maximum sizes. The problem is to assign the processes to the facilities, splitting them into batches, and scheduling these batches in order to produce the demands within the given deadlines. For the scheduling part of the problem we present an approach based on the following steps. First, a procedure to calculate the minimum number of batches needed to satisfy the demands is presented. Based on this, the given problem is modeled in two different ways: as a general shop scheduling problem with set-up times or as scheduling problem with positive time-lags. Finally, a two-phase tabu search method is presented which is based on the two different formulations of the problem. The method is tested on some real world data. This revised version was published online in June 2006 with corrections to the Cover Date.     

The selection and scheduling of telecommunication calls with time windows

We consider the bandwidth scheduling problem that consists of selecting and scheduling calls from a list of available calls to be routed on a bandwidth-capacitated telecommunication network in order to maximize profit. Each accepted call should be routed within a permissible scheduling time window for a required duration. To author's knowledge, this study represents the first work on bandwidth scheduling with time windows. We present an integer programming formulation of the problem. We also propose a solution procedure based on the well-established Lagrangean relaxation technique. The results of extensive computational experiments over a wide range of problem structures indicate that the procedure is both efficient and effective.     

Sample-path conservation laws,with applications to scheduling queues and fluid systems

The achievable-region approach, based on strong conservation laws, has most often been applied to stochastic scheduling and other control problems in the context of performance measures that are steady-state expected quantities. For some problems, however, strong conservation laws hold for performance measures at every time point on every sample path. We exploit this property to study optimal control for certain scheduling problems on a sample-path basis. Examples include preemptive scheduling to minimize a weighted sum of work in the system in each class, nonpreemptive scheduling to minimize a weighted sum of the number of customers in each class (when all classes have the same service-time distribution), and scheduling the processing of fluid in a multiclass fluid system operating in a random environment. The last problem is solved by considering the related Skorohod problem and its minimal solution. This revised version was published online in June 2006 with corrections to the Cover Date.     

Fuzzy project scheduling problem and its hybrid intelligent algorithm

Project scheduling problem is to determine the schedule of allocating resources so as to balance the total cost and the completion time. This paper considers a type of project scheduling problem with fuzzy activity duration times. According to some management goals, three types of fuzzy models are built to solve the project scheduling problem. Moreover, the technique of fuzzy simulation and genetic algorithm are integrated to design a hybrid intelligent algorithm to solve the fuzzy models. Finally, some numerical examples are given to illustrate the effectiveness of the algorithm.     

SEMI-DEFINITE RELAXATION ALGORITHM FOR SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES

The authors present a semi-definite relaxation algorithm for the scheduling problem with controllable times on a single machine. Their approach shows how to relate this problem with the maximum vertex-cover problem with kernel constraints (MKVC). The established relationship enables to transfer the approximate solutions of MKVC into the approximate solutions for the scheduling problem. Then, they show how to obtain an integer approximate solution for MKVC based on the semi-definite relaxation and randomized rounding technique.     

Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop

This paper describes a complex scheduling problem taken from a hospital diagnostic testing center that schedules hundreds of patients in an open shop environment consisting of multiple facilities and multiple processors. This scheduling problem, known as the multiprocessor open shop (MPOS) problem, is strongly NP-hard with few published results. Realizing that in many MPOS environments processing times are stage-dependent, not both job and stage-dependent, this paper examines a new class of problems for the MPOS—proportionate ones. This paper exploits the structural nature of the proportionate MPOS and defines new terms. Despite the enormous complexity of the MPOS problem, this work demonstrates that polynomial time algorithms exist for two special cases. Since other applications of this problem exist in service and manufacturing environments, solving the proportionate MPOS problem is not only significant in the theory of optimization, but also in many real-world applications.     

Single-facility scheduling by logic-based Benders decomposition

Logic-based Benders decomposition can combine mixed integer programming and constraint programming to solve planning and scheduling problems much faster than either method alone. We find that a similar technique can be beneficial for solving pure scheduling problems as the problem size scales up. We solve single-facility non-preemptive scheduling problems with time windows and long time horizons. The Benders master problem assigns jobs to predefined segments of the time horizon, where the subproblem schedules them. In one version of the problem, jobs may not overlap the segment boundaries (which represent shutdown times, such as weekends), and in another version, there is no such restriction. The objective is to find feasible solutions, minimize makespan, or minimize total tardiness.     

An Air Force Crew Allocation and Scheduling Problem

This paper considers an airline crew allocation and scheduling problem faced by certain divisions of the United States Air Force. Two variants of the problem under consideration were posed to us by the U.S. Air Force. This paper reports our experience with two heuristic methods developed, each applicable to either variant of the problem. Although the problem described herein is peculiar to this situation, the heuristic scheduling and dispatching rules developed have been found to be very effective and are generally applicable in other related contexts of routeing and crew and vehicle scheduling problems as well. The two algorithms developed have been applied to a coded set of real world data. The results indicate that each one of the two methods is preferable to the other for one of the two variants of the problem. This suggests an overall effective composite technique.     

A divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times

This article proposes lower bounds, as well as a divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times (MSPS). The heuristic is tested on randomly generated instances and compared with a previously published tabu search algorithm. Results show that the proposed heuristic is much faster than tabu search while providing similar quality solutions.     

Optimum Workforce Scheduling Under the (14, 21) Days-Off Timetable

An efficient optimum solution is presented for a real-life employee days-off scheduling problem with a three-week cycle. Over a given work cycle, each worker is given 14 successive workdays and 7 successive off days. This three-week days-off timetable is referred to as the (14, 21) schedule. Given different labor demands for each day of the week, the primary objective is to minimize the number of workers. The secondary objective is to reduce transportation cost by minimizing the number of active days-off patterns. The solution technique utilizes the dual LP solution to determine the minimum number of workers and feasible days-off assignments, without using linear or integer programming. The simple solution technique eliminates the need to use integer programming for this particular scheduling problem.     

A historical note on the complexity of scheduling problems

In 1972 E.M. Livshits and V.I. Rublinetsky published a paper in Russian, in which they presented linear-time reductions of the partition problem to a number of scheduling problems. Unaware of complexity theory, they argued that, since partition is not known to have a simple algorithm, one cannot expect to find simple algorithms for these scheduling problems either. Their work did not go completely unnoticed, but it received little recognition. We describe the approach and review the results.     

Tracking Demands in Optimal Control of Managerial Systems with Continuously-Divisible, Doubly Constrained Resources

The paper addresses problems of allocating continuously divisible resources among multiple production activities. The resources are allowed to be doubly constrained, so that both usage at every point of time and cumulative consumption over a planning horizon are limited as it is often the case in project and production scheduling. The objective is to track changing in time demands for the activities as closely as possible. We propose a general continuous-time model that states the problem in a form of the optimal control problem with non-linear speed-resource usage functions. With the aid of the maximum principle, properties of the solutions are derived to characterize optimal resource usage policies. On the basis of this analytical investigation, numerical scheduling methods are suggested and computationally studied. This revised version was published online in July 2006 with corrections to the Cover Date.     

平行机排序问题的列生成解法

基于整数规划的线性松弛,探讨求解大规模带权总完工时间排序问题的列生成算法的基本原理.然后,结合动态规划和分枝定界技术,对大规模排序问题P‖∑wiCj提出一类求解精确(最优)解的列生成算法.     

Scheduling medical students to teaching hospitals

This paper describes a scheduling technique that has been successfully used to allocate medical students to the teaching hospitals affiliated with a university. The problem is to schedule individuals so that (i) every student is assigned a preferred sequence of medical activities in specific hospitals, and (ii) the difference between the maximum number of students allowed at each available hospital-medical activity-period position and those allocated to these positions is both nonnegative and approximately the same. The contribution of the present work is in the formulation of the problem, and the resulting ease with which good solutions to large-scale scheduling problems can be generated. The mathematical formulation of the problem is presented first and subsequently, the solution strategy is described. The results for two large medical classes at the University of Montreal are also presented.     

Scheduling the flying squad nurses of a hospital using a multi-objective programming model

In this paper, we address the problem of scheduling nurses working on the flying squad of a hospital. Considering the large number of constraints, many of them being conflicting, the problem is formulated as a multi-objective programming problem with binary variables, where the objective function consists of a vector of objectives and penalty variables (deviation measures) provided by the soft constraints. Two approaches are considered to solve the problem: the weighted method and the sequential method. The best results are obtained with a mix of the two solving methods. Numerical results are presented. This revised version was published online in June 2006 with corrections to the Cover Date.     

An Integer Programming Approach to the Vehicle Scheduling Problem

This paper describes an integer programming formulation of the vehicle scheduling problem and illustrates how such a formulation can be extended to incorporate restrictions on work load, coverage and service that occur in real world vehicle scheduling problems. The integer programme is solved using the Revised Simplex method, additional constraints being introduced to retain integrality during convergence. The feasible region of this integer programme is initially restricted so that only routes constructed through sets of radially contiguous locations are considered. The effect of relaxing these over-constraints is explored. The method is demonstrated on fifteen problems ranging in size from 21 to 100 locations and the results generally show an improvement on previously published results. This is particularly true of the larger problems. This method compares favourably with other methods in computational efficiency.