Equivalence classes of problem instances for a continuous-time lot sizing and scheduling problem

In the context of a single machine, multi-item, continuous-time lot sizing and scheduling problem with a production rate alternating between the two values zero and full production rate, this paper identifies classes of equivalent problem instances which differ from one another in the way in which demand is represented. Each class contains an instance with a continuous cumulated demand function, and may contain demand functions with very different shapes, including functions with discontinuities. When approaching the problem (in order to solve it numerically, or to prove analytical results etc.), it therefore becomes possible to select, from many different representations, the problem instance which best meets the requirements of the applied method.     

On the characterization and generation of nurse scheduling problem instances

Due to its complexity and relevance in practice, many different procedures have been proposed in the operations research literature to solve the well-known nurse scheduling problem (NSP). The NSP assigns nurses to shifts per day maximizing the overall quality of the roster while taking various constraints into account. The often highly case-specific workplace conditions in hospital departments have resulted in the development of dedicated (meta-)heuristics to find a workable schedule in an acceptable time limit. However, in spite of research community posing a growing need for benchmarking, these procedures lack any base for comparison.     

Solution of a large-scale two-stage decision and scheduling problem using decomposition

In this paper, we develop a decomposition technique for the solution of a two-stage decision and scheduling problem in production environments. A tree search heuristic based on the decomposition approach is developed. We illustrate the procedure on the industry example of flat glass production.     

An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances

In this paper, an overview is presented of the existing metaheuristic solution procedures to solve the multi-mode resource-constrained-project scheduling problem, in which multiple execution modes are available for each of the activities of the project. A fair comparison is made between the different metaheuristic algorithms on the existing benchmark datasets and on a newly generated dataset. Computational results are provided and recommendations for future research are formulated.     

Solving a manpower scheduling problem for airline catering using metaheuristics

We study a manpower scheduling problem with job time windows and job-skills compatibility constraints. This problem is motivated by airline catering operations, whereby airline meals and other supplies are delivered to aircrafts on the tarmac just before the flights take-off. Jobs (flights) must be serviced within a given time-window by a team consisting of a driver and loader. Each driver/loader has the skills to service some, but not all, of the airline/aircraft/configuration of the jobs. Given the jobs to be serviced and the roster of workers for each shift, the problem is to form teams and assign teams and start-times for the jobs, so as to service as many flights as possible. Only teams with the appropriate skills can be assigned to a flight. Workload balance among the teams is also a consideration. We present model formulations and investigate a tabu search heuristic and a simulated annealing heuristic approach to solve the problem. Computational experiments show that the tabu search approach outperforms the simulated annealing approach, and is capable of finding good solutions.     

Reducing the feasible region to a scheduling problem

A special class of scheduling problems is considered. We consider cycle-free sets of fronts correspond to the orderings of a network. If the project is recourse-constrained, the same cycle-free set of fronts can correspond to different orderings. Some cycle-free sets of fronts can be subsets of others. The goal of the paper is to characterize maximal cycle-free sets of fronts because only those are essential for obtaining an optimal schedule.     

Solving multi-criteria scheduling flow shop problem through compromise programming and satisfaction functions

The multi-criteria scheduling problem is one of the main research subjects in the field of multiple objectives programming. Several procedures have been developed to deal with this type of problem where some conflicting criteria have to be optimized simultaneously. The aim of our paper is to propose an aggregation procedure that integrates three different criteria to find the best sequence in a flow shop production environment. The compromise programming model and the concept of satisfaction functions will be utilized to integrate explicitly the manager’s preferences according to the deviations between the achievement and the aspiration levels of the following criteria: Makespan, total flow time and total tardiness.     

A network solution to a general vehicle scheduling problem

Dantzig and Fulkerson and later Bellmore et al. have shown that certain vehicle (tanker) scheduling problems can be formulated as minimum cost flow problems on a network. In this paper, the results of Dantzig and Fulkerson are extended to the case where more than one type of vehicle can be used in the determination of an optimal fleet. (In tanker scheduling terminology; how many small, medium and large tankers would form an optical fleet.) It is seen how the problem can be formulated as a modified transportation problem where flow in some arcs is conditioned to there being flow on certain other arcs. These “conditional” transportation problems were solved directly as linear programs and showed the peculiarity of terminating all integer in spite of having a constraint matrix, which does not satisfy the well known sufficient conditions for urimodularity. We discuss the implementation of the model and its empirical results.     

On the interactive solution to a multicriteria scheduling problem

Summary A mixed integer multiple criteria model is formulated for scheduling problems. Its solution is obtained by an interactive method based on the Tchebycheff-approximation. For solving greater problems some modifications are discussed at the end of the paper, which are essentially based on the notion of heuristic efficiency.

---

Zusammenfassung Da bei Ablaufplanungsproblemen häufig mehrere Zielsetzungen zu beachten sind, wird im folgenden Beitrag hierzu ein gemischt-ganzzahliges multikriterielles Entscheidungsmodell formuliert. Seine Lösung erfolgt mit Hilfe eines interaktiven Verfahrens. Zur numerischen Lösung größerer Problemstellungen sind einzelne Verfahrensmodifikationen erforderlich, die im wesentlichen auf dem im letzten Abschnitt eingeführten Begriff der heuristischen Effizienz aufbauen.

     

Extension of algorithm list scheduling for a semi-online scheduling problem

A general algorithm, called ALG, for online and semi-online scheduling problem Pm||C _max with m ≥ 2 is introduced. For the semi-online version, it is supposed that all job have their processing times within the interval [p, rp], where p > 0,1 < r ≤ m/m − 1. ALG is a generalization of LS and is optimal in the sense that there is not an algorithm with smaller competitive ratio than that of ALG.     

Complexity results on restricted instances of a paint shop problem for words

We study the following problem: an instance is a word with every letter occurring twice. A solution is a 2-coloring of its letters such that the two occurrences of every letter are colored with different colors. The goal is to minimize the number of color changes between adjacent letters.This is a special case of the paint shop problem for words, which was previously shown to be NP-complete. We show that this special case is also NP-complete and even APX-hard. Furthermore, derive lower bounds for this problem and discuss a transformation into matroid theory enabling us to solve some specific instances within polynomial time.     

Dual decomposition of a single-machine scheduling problem

We design a fast ascent direction algorithm for the Lagrangian dual problem of the single-machine scheduling problem of minimizing total weighted completion time subject to precedence constraints. We show that designing such an algorithm is relatively simple if a scheduling problem is formulated in terms of the job completion times rather than as an 0–1 linear program. Also, we show that upon termination of such an ascent direction algorithm we get a dual decomposition of the original problem, which can be exploited to develop approximative and enumerative approaches for it. Computational results exhibit that in our application the ascent direction leads to good Lagrangian lower and upper bounds.     

Approximate solution of a resource-constrained scheduling problem

This paper is devoted to the approximate solution of a strongly NP-hard resource-constrained scheduling problem which arises in relation to the operability of certain high availability real time distributed systems. We present an algorithm based on the simulated annealing metaheuristic and, building on previous research on exact solution methods, extensive computational results demonstrating its practical ability to produce acceptable solutions, in a precisely defined sense. Additionally, our experiments are in remarkable agreement with certain theoretical properties of our simulated annealing scheme. The paper concludes with a short discussion on further research. This research was supported in part by Association Nationale de la Recherche Technique grant CIFRE-121/2004.     

Models and algorithms for a staff scheduling problem

We present mathematical models and solution algorithms for a family of staff scheduling problems arising in real life applications. In these problems, the daily assignments to be performed are given and the durations (in days) of the working and rest periods for each employee in the planning horizon are specified in advance, whereas the sequence in which these working and rest periods occur, as well as the daily assignment for each working period, have to be determined. The main objective is the minimization of the number of employees needed to perform all daily assignments in the horizon. We decompose the problem into two steps: the definition of the sequence of working and rest periods (called pattern) for each employee, and the definition of the daily assignment to be performed in each working period by each employee. The first step is formulated as a covering problem for which we present alternative ILP models and exact enumerative algorithms based on these models. Practical experience shows that the best approach is based on the model in which variables are associated with feasible patterns and generated either by dynamic programming or by solving another ILP. The second step is stated as a feasibility problem solved heuristically through a sequence of transportation problems. Although in general this procedure may not find a solution (even if one exists), we present sufficient conditions under which our approach is guaranteed to succeed. We also propose an iterative heuristic algorithm to handle the case in which no feasible solution is found in the second step. We present computational results on real life instances associated with an emergency call center. The proposed approach is able to determine the optimal solution of instances involving up to several hundred employees and a working period of up to 6 months. Mathematics Subject Classification (2000): 90B70, 90C10, 90C27, 90C39, 90C57, 90C59     

Modeling and algorithmic development of a staff scheduling problem

The problem of scheduling workers at a hub of a trucking system for the stripping and loading of the trucks and the determination of the optimal number of workers is a difficult problem. The trucks arrive at the facility at different (but known) times and may have their own scheduled departure times. This problem is like a set partitioning problem but with a side constraint pertaining to the dynamic arrival of the trucks. We develop a procedure to solve this problem that is based on the column generation technique, and the solution of a set covering problem to obtain the integer solution. The performance of the procedure is demonstrated by applying it to the real-life data obtained from a trucking company. Its effectiveness is illustrated by comparing it with a lower bound and a well-known heuristic procedure.     

On a resource-constrained scheduling problem with application to distributed systems reconfiguration

This paper is devoted to the study of a resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high availability real-time distributed systems. Informally, this problem consists, starting from an arbitrary initial distribution of processes on the processors of a distributed system, in finding the least disruptive sequence of operations (non-impacting process migrations or temporary process interruptions) at the end of which the system ends up in another predefined arbitrary state. The main constraint is that the capacity of the processors must not be exceeded during the reconfiguration. After a brief survey of the literature, we prove the NP-hardness of the problem and exhibit a few polynomial special cases. We then present a branch-and-bound algorithm for the general case along with computational results demonstrating its practical relevance. The paper is concluded by a discussion on further research.     

Green functions of a quasi-static problem

In this paper Green functions are constructed in analytic form for a deformable half-plane of a quasi-static problem of thermoelasticity when the heat flow on the boundary x₂=0 of the half-plane is zero. To construct the Green functions, certain integral representations are used whose kernels are known Green functions of the corresponding problems of elasticity theory. The functions constructed make it possible to obtain a wide class of new solutions of boundary-value problems of thermoelasticity, in particular solutions for a piecewise homogeneous half-plane. Bibliography: 6 titles. Translated fromObchyslyuwval’na ta Pryklandna Matematyka, No. 77, 1993, pp. 97–104.     

The counting complexity of a simple scheduling problem

Let T be a set of tasks. Each task has a non-negative processing time and a deadline. The problem of determining whether or not there is a schedule of the tasks in T such that a single machine can finish processing each of them before its deadline is polynomially solvable. We prove that counting the number of schedules satisfying this condition is #P-complete.     

Learning and forgetting effects on a group scheduling problem

This paper proposes to investigate learning and forgetting effects on the problem of scheduling families of jobs on a single machine to minimize total completion time of jobs. A setup time is incurred whenever the single machine transfers job processing from a family to another family. To analyze the impact of learning and forgetting on this group scheduling problem, we structure three basic models and make some comparisons through computational experiments. The three models, including no forgetting, total forgetting and partial forgetting, assume that the processing time of a job is dependent on its position in a schedule. Some scheduling rules and a lower bound are derived in order to constitute our branch-and-bound algorithm for searching an optimal sequence. In addition, an efficient and simply-structured heuristic is also built to find a near-optimal schedule.     

Energetic reasoning and bin-packing problem, for bounding a parallel machine scheduling problem

This paper deals with an extension of energetic reasoning, using some efficient lower bounds of the bin-packing problem, to get tight lower bounds for the P|r _i , q _i |C _max. The link between P||C _max and bin-packing problem is well-known. Our purpose is to extend the use of efficient lower bounds of the bin-packing problem to P|r _i , q _i |C _max. We focus on some time-intervals, to compute the mandatory parts of activities within this time-interval and then to deduce an associated bin-packing instance. Thus, lower bounds of the bin-packing problem are used to get new satisfiability tests for the parallel machine problem. We also propose to extend the classical time-bound adjustments of release dates and deadlines to efficiently use bin-packing lower bounds. Experimental results that prove the efficiency of our approach on several kind of instances are reported.