A Generalized Machine-Scheduling Algorithm

It is proposed to treat a general machine-job-scheduling problem using a branch-and-bound method. Here the general problem is that in which the routing of any job through the machines is specified in advance but is independent of the routing of any other job. In addition there is no requirement for the job to visit all machines. Since any two operations to be performed on the same machine cannot be performed simultaneously, the set of all schedules can be divided into two subsets-one in which the pair of operations is performed in one order and the second in which the order is reversed. This division corresponds to branching in the method. For each of the new subsets formed by branching a lower bound on the duration of all schedules in the subset is calculated and the schedule with minimum duration is found by successive subdivision. An illustrative example is solved and the method is compared to other published general methods.     

The Solution of a Railway Locomotive Scheduling Problem

A method is described for finding a minimum cost set of schedules for railway locomotives to work a given set of trains. The times at which the trains start may be fixed or variable. A heuristic method, based on a linear programming model, is described. This gives good integer solutions to the problem.     

Nondominated Schedules for a Job-Shop with Two Competing Users

We consider the scenario where two users compete to perform their respective jobs on a common set of resources. The job for each user has a due-date and the cost function associated with the due-date is quasi-convex (i.e., it has a single local minimum). We characterize the set of nondominated schedules over which the users may negotiate and develop a polynomial algorithm to find this nondominated set.     

Orthogonal schedules in single round robin tournaments

A measure for the flexibility of a Home-Away Pattern set (HAP-set) is the width. The width of a HAP-set equals the size of the largest set of schedules compatible with the HAP-set, for which no match is scheduled in the same round in any two schedules. We prove lower and upper bounds on the width, and identify HAP-sets with largest possible width when the number of teams is a power of 2.     

Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria

In this paper, we consider a rescheduling problem where a set of jobs has already been assigned to unrelated parallel machines. When a disruption occurs on one of the machines, the affected jobs are rescheduled, considering the efficiency and the schedule deviation measures. The efficiency measure is the total flow time, and the schedule deviation measure is the total disruption cost caused by the differences between the initial and current schedules. We provide polynomial-time solution methods to the following hierarchical optimization problems: minimizing total disruption cost among the minimum total flow time schedules and minimizing total flow time among the minimum total disruption cost schedules. We propose exponential-time algorithms to generate all efficient solutions and to minimize a specified function of the measures. Our extensive computational tests on large size problem instances have revealed that our optimization algorithm finds the best solution by generating only a small portion of all efficient solutions.     

A repairing technique for the local search of the job-shop problem

The local search technique has become a widely used tool for solving many combinatorial optimization problems. In the case of the job-shop the implementation of such a technique is not straightforward at all due to the existence of the technological constraints among the operations that belong to the same job. Their presence renders a certain set of schedules infeasible. Consequently, special attention is required when defining optimization algorithms to prevent the possibility of reaching an infeasible schedule during execution. Traditionally, the problem is tackled on the neighborhood level by using only a limited set of moves for which feasibility inherently holds. This paper proposes an alternative way to avoid infeasibility by incorporating a repairing technique into the mechanism for applying moves to a schedule. Whenever an infeasible move is being applied, a repairing mechanism rearranges the underlying schedule in such a way that the feasibility of the move is restored. The possibility of reaching infeasible solutions is, therefore, eliminated on the lowest possible conceptual level. Consequently, neighborhood functions need not to be constrained to a limited set of feasible moves any more.     

Selecting and adapting weekly work schedules with working time accounts: A case of a retail clothing chain

A case of selection and adaptation of weekly work schedules is presented. Weekly work schedules in two franchises of an important retail clothing chain have to be established. Working time accounts are used: each week, an employee can owe the company a certain number of hours or vice versa. Nevertheless, over a certain threshold, the hours have to be paid for by the company and the account balance returns to zero. A minimum and desired level of capacity of employees is contemplated. Hierarchically, the planned capacity must attempt to reach the minimum level; then it must fit a desired level as much as possible. At present, the task of allocation and the final adjustment of schedules is done manually, which is difficult, ineffective and often inaccurate. The procedure proposed is divided into two phases. Firstly, a work schedule, selected from a list, is assigned to each worker; a mixed linear program, followed by a local optimization process, is used. In the second phase, the work schedules are modified according to predefined rules: if there is a surplus of capacity, work schedules are reduced, and if there is a shortage, work schedules are extended. The company considers the results to be satisfactory.     

Schedule execution for two-machine flow-shop with interval processing times

This paper addresses the issue of how to best execute the schedule in a two-phase scheduling decision framework by considering a two-machine flow-shop scheduling problem in which each uncertain processing time of a job on a machine may take any value between a lower and upper bound. The scheduling objective is to minimize the makespan. There are two phases in the scheduling process: the off-line phase (the schedule planning phase) and the on-line phase (the schedule execution phase). The information of the lower and upper bound for each uncertain processing time is available at the beginning of the off-line phase while the local information on the realization (the actual value) of each uncertain processing time is available once the corresponding operation (of a job on a machine) is completed. In the off-line phase, a scheduler prepares a minimal set of dominant schedules, which is derived based on a set of sufficient conditions for schedule domination that we develop in this paper. This set of dominant schedules enables a scheduler to quickly make an on-line scheduling decision whenever additional local information on realization of an uncertain processing time is available. This set of dominant schedules can also optimally cover all feasible realizations of the uncertain processing times in the sense that for any feasible realizations of the uncertain processing times there exists at least one schedule in this dominant set which is optimal. Our approach enables a scheduler to best execute a schedule and may end up with executing the schedule optimally in many instances according to our extensive computational experiments which are based on randomly generated data up to 1000 jobs. The algorithm for testing the set of sufficient conditions of schedule domination is not only theoretically appealing (i.e., polynomial in the number of jobs) but also empirically fast, as our extensive computational experiments indicate.     

On some properties of optimal schedules in the job shop problem with preemption and an arbitrary regular criterion

Optimal schedules in the job shop problem with preemption and with the objective of minimizing an arbitrary regular function of operation completion times are studied. It is shown that for any instance of the problem there always exists an optimal schedule that meets several remarkable properties. Firstly, each changeover date coincides with the completion time of some operation, and so, the number of changeover dates is not greater than the total number of operations, while the total number of interruptions of the operations is no more than the number of operations minus the number of jobs. Secondly, every changeover date is “super-integral”, which means that it is equal to the total processing time of some subset of operations. And thirdly, the optimal schedule with these properties can be found by a simple greedy algorithm under properly defined priorities of operations on machines. It is also shown that for any instance of the job shop problem with preemption allowed there exists a finite set of its feasible schedules which contains at least one optimal schedule for any regular objective function (from the continuum set of regular functions).     

A priority list based heuristic for the job shop problem

A priority list for the job shop scheduling problem is defined to be any permutation of a set of symbols where the symbol for each job appears as many times as the number of its operations. Every priority list can be associated in a natural way with a feasible schedule, and every feasible schedule arises in this way. Priority lists are therefore a representation of feasible schedules that avoid the problems normally associated with schedule infeasibility. As a result, the three ingredients of local search heuristics, namely picking initial starting schedules, constructing search neighbourhoods and computing makespans, become faster and easier when performed in the space of priority lists rather than in the space of feasible schedules. As an illustration of their usefulness, a priority list based simulated annealing heuristic is presented, which, although simple, is competitive with the current leading schedule based simulated annealing and tabu search heuristics.     

An efficient and flexible mechanism for constructing membership functions

This paper introduces a Bézier curve-based mechanism for constructing membership functions of convex normal fuzzy sets. The mechanism can fit any given data set with a minimum level of discrepancy. In the absence of data, the mechanism can be intuitively manipulated by the user to construct membership functions with the desired shape. Some numerical experiments are included to compare the performance of the proposed mechanism with conventional methods.     

Developing work schedules for an inter-city transit system with multiple driver types and fleet types

In developing work schedules, the job assignment flexibility exploits the variety of available skills, thus enabling the assignment of workers to perform different jobs. In this study, we investigate the problem of finding the mix of primary and secondary jobs in short term work schedules to meet, at minimum cost, the daily service requirements of an inter-city bus transit firm in Andra Pradesh India operating multiple fleet types. We formulate the problem as a set covering model with resource allocation constraints. We develop a branch-and-price procedure to solve the model. Computational results are provided.     

The Dial-a-Ride Problem (DARP): Variants,modeling issues and algorithms

The Dial-a-Ride Problem (DARP) consists of designing vehicle routes and schedules for n users who specify pick-up and drop-off requests between origins and destinations. The aim is to plan a set of m minimum cost vehicle routes capable of accommodating as many users as possible, under a set of constraints. The most common example arises in door-to-door transportation for elderly or disabled people. The purpose of this article is to review the scientific literature on the DARP. The main features of the problem are described and classified and some modeling issues are discussed. A summary of the most important algorithms is provided.AMS classification: 90B06, 90C27, 90C59     

The dial-a-ride problem: models and algorithms

The Dial-a-Ride Problem (DARP) consists of designing vehicle routes and schedules for n users who specify pickup and delivery requests between origins and destinations. The aim is to plan a set of m minimum cost vehicle routes capable of accommodating as many users as possible, under a set of constraints. The most common example arises in door-to-door transportation for elderly or disabled people. The purpose of this article is to review the scientific literature on the DARP. The main features of the problem are described and a summary of the most important models and algorithms is provided. This is an updated version of a paper that appeared in 4OR 1:89–101, 2003.     

The relation of time indexed formulations of single machine scheduling problems to the node packing problem

 The relation of time indexed formulations of nonpreemptive single machine scheduling problems to the node packing problem is established and then used to provide simple and intuitive alternate proofs of validity and maximality for previously known results on the facial structure of the scheduling problem. Previous work on the facial structure has focused on describing the convex hull of the set of feasible partial schedules, schedules in which not all jobs have to be started. The equivalence between the characteristic vectors of this set and those of the set of feasible node packings in a graph whose structure is determined by the parameters of the scheduling problem is established. The main contribution of this paper is to show that the facet inducing inequalities for the convex hull of the set of feasible partial schedules that have integral coefficients and right hand side 1 or 2 are the maximal clique inequalities and the maximally and sequentially lifted 5-hole inequalities of the convex hull of the set of feasible node packings in this graph respectively. Received: September 10, 2000 / Accepted: April 20, 2002 Published online: September 27, 2002 Key words. scheduling – node packing – polyhedral methods – facet defining graphs – lifted valid inequalities – facet inducing inequalities}     

Active and stable project scheduling

The paper proposes a new classification of schedules for resource-constrained project scheduling problems with minimum and maximum time lags between project activities and regular and different types of nonregular objective functions. The feasible region of the scheduling problems represents a (generally disconnected) union of polytopes. In addition to the well-known concepts of active and semiactive schedules, pseudoactive and quasiactive as well as stable, semistable, pseudostable, and quasistable schedules are introduced. The (quasi-, pseudo-, semi-)active schedules are related to different types of left-shifts of sets of activities and correspond to minimal points of certain subsets of the feasible region. The (quasi-, pseudo-, semi-)stable schedules do not allow oppositely directed shifts and correspond to extreme points of certain subsets of the feasible region. The different sets of schedules contain optimal schedules for project scheduling problems which differ in their objective functions. The correspondence between those sets of schedules and vertices of specific polyhedral subsets of the feasible region can be exploited for analyzing schedule generation schemes which have been developed recently for finding solutions to the different classes of project scheduling problems.     

Transformation of Quasiconvex Functions to Eliminate Local Minima

Quasiconvex functions present some difficulties in global optimization, because their graph contains “flat parts”; thus, a local minimum is not necessarily the global minimum. In this paper, we show that any lower semicontinuous quasiconvex function may be written as a composition of two functions, one of which is nondecreasing, and the other is quasiconvex with the property that every local minimum is global minimum. Thus, finding the global minimum of any lower semicontinuous quasiconvex function is equivalent to finding the minimum of a quasiconvex function, which has no local minima other than its global minimum. The construction of the decomposition is based on the notion of “adjusted sublevel set.” In particular, we study the structure of the class of sublevel sets, and the continuity properties of the sublevel set operator and its corresponding normal operator.     

A Population-Based Approach to the Resource-Constrained Project Scheduling Problem

We present a population-based approach to the RCPSP. The procedure has two phases. The first phase handles the initial construction of a population of schedules and these are then evolved until high quality solutions are obtained. The evolution of the population is driven by the alternative application of an efficient improving procedure for locally improving the use of resources, and a mechanism for combining schedules that blends scatter search and path relinking characteristics. The objective of the second phase is to explore in depth those vicinities near the high quality schedules. Computational experiments on the standard j120 set, generated using ProGen, show that our algorithm produces higher quality solutions than state-of-the-art heuristics for the RCPSP in an average time of less than five seconds.     

Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors

In the classical scheduling theory, it is widely assumed that a task can be processed by only one processor at a time. With the rapid development of technology, this assumption is no longer valid. In this work we present a problem of scheduling tasks, each of which requires for its processing a set of processors simultaneously and which can be executed on several alternative sets of processors. Scheduling algorithms based on dynamic and linear programming are presented that construct minimum length non-preemptive and preemptive schedules, respectively. Results of computational experiments are also reported.This research was partially supported by a KBN grant and by project CRIT.     

A branching scheme for finding cost-minimal round robin tournaments

Single round robin tournaments are a well known class of sports leagues schedules. We consider leagues with a set T of n teams where n is even. Costs are associated to each possible match. The goal is to find the minimum cost tournament among those having the minimum number of breaks. We pick up structural properties of home–away-pattern sets having the minimum number of breaks. A branching idea using these properties is developed in order to guide branching steps on the first levels of a branch-and-bound tree in order to avoid nodes corresponding to infeasible subproblems.