Tabu search for a class of scheduling problems

Scheduling problems are often modeled as resourceconstrained problems in which critical resource assignments to tasks are known and the best assignment of resource time must be made subject to these constraints. Generalization toresource scheduling, where resource assignments are chosen concurrently with times results is a problem which is much more difficult. A simplified model of the general resource scheduling model is possible, however, in which tasks must be assigned a singleprimary resource, subject to constraints resulting from preassignment ofsecondary, or auxiliary, resources. This paper describes extensions and enhancements of tabu search for the special case of the resource scheduling problem described above. The class of problems is further restricted to those where it is reasonable to enumerate both feasible time and primary resource assignments. Potential applications include shift oriented production and manpower scheduling problems as well as course scheduling where classrooms (instructors) are primary and instructors (rooms) and students are secondary resources. The underlying model is a type of quadratic multiple choice problem which we call multiple choice quadratic vertex packing (MCQVP). Results for strategic oscillation and biased candidate sampling strategies are shown for reasonably sized real and randomly generated, synthetic, problem instances. The strategies are compared with other variations using consistent measures of solution time and quality developed for this study.     

A survey of variants and extensions of the resource-constrained project scheduling problem

The resource-constrained project scheduling problem (RCPSP) consists of activities that must be scheduled subject to precedence and resource constraints such that the makespan is minimized. It has become a well-known standard problem in the context of project scheduling which has attracted numerous researchers who developed both exact and heuristic scheduling procedures. However, it is a rather basic model with assumptions that are too restrictive for many practical applications. Consequently, various extensions of the basic RCPSP have been developed. This paper gives an overview over these extensions. The extensions are classified according to the structure of the RCPSP. We summarize generalizations of the activity concept, of the precedence relations and of the resource constraints. Alternative objectives and approaches for scheduling multiple projects are discussed as well. In addition to popular variants and extensions such as multiple modes, minimal and maximal time lags, and net present value-based objectives, the paper also provides a survey of many less known concepts.     

Building Better Nurse Scheduling Algorithms

The aim of this research is twofold: Firstly, to model and solve a complex nurse scheduling problem with an integer programming formulation and evolutionary algorithms. Secondly, to detail a novel statistical method of comparing and hence build better scheduling algorithms by identifying successful algorithm modifications. The comparison method captures the results of algorithms in a single figure that can then be compared using traditional statistical techniques. Thus, the proposed method of comparing algorithms is an objective procedure designed to assist in the process of improving an algorithm. This is achieved even when some results are non-numeric or missing due to infeasibility. The final algorithm outperforms all previous evolutionary algorithms, which relied on human expertise for modification.     

Metaheuristics for meltshop scheduling in the steel industry

The scheduling of a meltshop at an integrated steel plant is a very complex and important logistical industrial problem. This problem requires the synchronization of several steelmaking furnaces, degassing facilities, ladle treatment stations, and continuous casters. In this paper, we discuss how an efficient domain-specific heuristic is combined with metaheuristic approaches in a prototype scheduling model. Specifically, given preliminary schedules for the continuous casters, the model determines the allocation, sequencing, and scheduling of batches of steel at the basic oxygen steelmaking furnaces, the degassing facilities, and the ladle treatment stations. It also makes the appropriate schedule modifications at the continuous casters. Computational results will be discussed.     

A subproblem-centric model and approach to the nurse scheduling problem

The number of hospitals in Japan exceeds 10,000, and every month nurses are scheduled to shifts in about 30,000 units in total. There is serious demand for automating this scheduling task. In this paper, we introduce a mathematical programming formulation of the nurse scheduling problem in Japan, and develop a meta-heuristic approach to solve the problem. This scheduling problem is a hard combinatorial problem due to tight constraints involving such factors as the skill level of a team, the need to balance workload among nurses, and the consideration of nurses' preferences, even though the number of the nurses to be scheduled is not large, at between 20 and 40. The performance of our approach is demonstrated by the successful solution of data taken from actual scheduling problems. The proposed model and approach can be adapted for the majority of hospitals in Japan, as well as for some hospitals in other countries, and is likely applicable to many other scheduling problems in the fields of business and logistics. Key words.nurse scheduling – block-angular problem – subproblem – integer programming – relaxation – tabu search – branch-and-boundMathematics Subject Classification (1991):20E28, 20G40, 20C20     

Heuristics for multimode scheduling problems with dedicated resources

We study scheduling problems with multiple modes and dedicated resources arising in production and project management, which constitute a special class of the general multimode resource-constrained project scheduling problem. A task may require simultaneously a set of discrete, renewable resources to be processed and the processing can be performed in different modes, that is with different resource sets, processing times, or costs. Precedence constraints can exist among tasks. The total budget that can be allocated to the project can be limited. The problem consists of identifying a mode for each task and a starting time for its processing respecting precedence, resource, and budget constraints. A graph model and an iterative solution scheme are presented. Specific heuristic algorithms for the cases with and without budget constraints are given and computational results are discussed.     

Integrated production and material handling scheduling using mathematical programming and constraint programming

In this article, we propose an integrated formulation of the combined production and material handling scheduling problems. Traditionally, scheduling problems consider the production machines as the only constraining resource. This is however no longer true as material handling vehicles are becoming more and more valuable resources requiring important investments. Their operations should be optimized and above all synchronized with machine operations. In the problem addressed in this paper, a job shop context is considered. Machines and vehicles are both considered as constraining resources. The integrated scheduling problem is formulated as a mathematical programming model and as a constraint programming model which are compared for optimally solving a series of test problems. A commercial software (ILOG OPLStudio) was used for modeling and testing both models.     

Heuristic algorithms for a complex parallel machine scheduling problem

In this work we present a new scheduling model for parallel machines, which extends the multiprocessor scheduling problem with release times for minimizing the total tardiness, and also extends the problem of vehicle routing with time windows. This new model is motivated by a resource allocation problem, which appears in the service sector. We present two class of heuristic algorithms for the solution of the problem, the first class is a class of greedy algorithms, the second class is based on the solutions of linear assignment problems. Furthermore we give a rescheduling algorithm, which improves a given feasible solution of the problem. This research has been supported by the Hungarian National Foundation for Scientific Research, Grant T046405.     

Reducing patient-flow delays in surgical suites through determining start-times of surgical cases

A scheduling strategy to determine starting times of surgeries in multiple operating rooms (OR) is presented. The constraints are resource limit of a downstream facility, post-anesthesia care unit (PACU), and the service time uncertainties. Given sets of surgeries that need to be done on a day, this problem is formulated as a flexible job shop model with fuzzy sets. Patient-waitings in the process flow, clinical resource idling, and total completion times are considered for evaluation. This multi-objective problem is solved by a two-stage decision process. A genetic algorithm is used for determining relative order of surgeries in the first stage and definite starting times for all the surgical cases are obtained by a decision-heuristic in the second stage. The resultant schedule is evaluated by a Monte-Carlo simulation. The performance is shown to be better than our previous approach, a simulation based scheduling which already outperforms simple scheduling rules in regional hospitals. Additionally, the ratio of PACU to OR is examined using the proposed scheduling strategy.     

人力资源约束下的项目群调度问题建模与求解

基于人员胜任力是影响工作绩效的关键因素,将资源受限项目调度问题中的可更新资源通过一系列科学合理的方法或者手段转变为存在胜任力差异的人力资源,由此构建起一个强调胜任力差异的人力资源约束项目调度问题模型,此模型最突出的优势在于选取了能够客观合理评估人员胜任力的指标,提供了严谨科学的关系式,将复杂的多项目总工期与总成本的双目标最小化问题转换为综合指标单目标最大化问题,建立数学优化模型,采用遗传算法求解。通过算例研究证实,相较于传统多模式模型,基于人员胜任力水平差异的模型明显更胜一筹,其优势集中表现为最优工期更短、最优成本更低。考虑了胜任力差异的数学优化模型更符合研发项目群管理实践,同时遗传算法在求解方面不仅效率高,并且更容易获得客观准确的结果。     

A branch-and-price approach for integrating nurse and surgery scheduling

A common problem at hospitals is the extreme variation in daily (even hourly) workload pressure for nurses. The operating room is considered to be the main engine and hence the main generator of variance in the hospital. The purpose of this paper is threefold. First of all, we present a concrete model that integrates both the nurse and the operating room scheduling process. Second, we show how the column generation technique approach, one of the most employed exact methods for solving nurse scheduling problems, can easily cope with this model extension. Third, by means of a large number of computational experiments we provide an idea of the cost saving opportunities and required solution times.     

Using a MILP model to establish a framework for an annualised hours agreement

Production flexibility is essential for industrial companies that have to deal with seasonal demand. Human resources are one of the main sources of flexibility. Annualising working hours (i.e., the possibility of irregularly distributing the total number of working hours over the course of a year) is a tool that provides flexibility to organizations; it enables a firm to adapt production capacity to fluctuations in demand. However, it can imply a worsening of the staff’s working conditions. To take the human aspect into account, the planning and scheduling of working time should comply with constraints derived from the law or from a collective bargaining agreement. Furthermore, new and more difficult working-time planning and scheduling problems are arising. This paper proposes a mixed-integer linear program model to solve the problem of planning the production and the working hours of a human team that operates in a multi-product process. Solving the model for different settings provides the essential quantitative information to negotiate the best conditions of the annualised hours system (the elements to establish the trade-off between weekly flexibility and economic or working-time reduction compensation can be obtained). The results achieved in a computational experiment were very satisfactory.     

Scheduling for single agile satellite,redundant targets problem using complex networks theory

Scheduling for the Earth observation satellites (EOSs) imaging mission is a complicated combinatorial optimization problem, especially for the agile EOSs (AEOSs). The increasing observation requirements and orbiting satellites have exacerbated the scheduling complexity in recent years. In this paper, the single agile satellite, redundant observation targets scheduling problem is studied. We introduce the theory of complex networks and find similarities between AEOS redundant targets scheduling problem and the node centrality ranking problem. Then we model this problem as a complex network, regarding each node as a possible observation opportunity, and define two factors, node importance factor and target importance factor, to describe the node/target importance. Based on the two factors, we propose a fast approximate scheduling algorithm (FASA) to obtain the effective scheduling results. Simulation results indicate the FASA is quite efficient and with broad suitability. Our work is helpful in the EOSs and AEOSs scheduling problems by using complex network knowledge.     

Machine scheduling with resource dependent processing times

We consider machine scheduling on unrelated parallel machines with the objective to minimize the schedule makespan. We assume that, in addition to its machine dependence, the processing time of any job is dependent on the usage of a discrete renewable resource, e.g. workers. A given amount of that resource can be distributed over the jobs in process at any time, and the more of that resource is allocated to a job, the smaller is its processing time. This model generalizes the classical unrelated parallel machine scheduling problem by adding a time-resource tradeoff. It is also a natural variant of a generalized assignment problem studied previously by Shmoys and Tardos. On the basis of an integer linear programming formulation for a relaxation of the problem, we use LP rounding techniques to allocate resources to jobs, and to assign jobs to machines. Combined with Graham’s list scheduling, we show how to derive a 4-approximation algorithm. We also show how to tune our approach to yield a 3.75-approximation algorithm. This is achieved by applying the same rounding technique to a slightly modified linear programming relaxation, and by using a more sophisticated scheduling algorithm that is inspired by the harmonic algorithm for bin packing. We finally derive inapproximability results for two special cases, and discuss tightness of the integer linear programming relaxations.     

Time slack-based techniques for robust project scheduling subject to resource uncertainty

The resource-constrained project scheduling problem (RCPSP) has been the subject of a great deal of research during the previous decades. This is not surprising given the high practical relevance of this scheduling problem. Nevertheless, extensions are needed to be able to cope with situations arising in practice such as multiple activity execution modes, activity duration changes and resource breakdowns. In this paper we analytically determine the impact of unexpected resource breakdowns on activity durations. Furthermore, using this information we develop an approach for inserting explicit idle time into the project schedule in order to protect it as well as possible from disruptions caused by resource unavailabilities. This strategy will be compared to a traditional simulation-based procedure and to a heuristic developed for the case of stochastic activity durations.     

A market-based multi-agent system model for decentralized multi-project scheduling

We consider a multi-project scheduling problem, where each project is composed of a set of activities, with precedence relations, requiring specific amounts of local and shared (among projects) resources. The aim is to complete all the project activities, satisfying precedence and resource constraints, and minimizing each project schedule length. The decision making process is supposed to be decentralized, with as many local decision makers as the projects. A multi-agent system model, and an iterative combinatorial auction mechanism for the agent coordination are proposed. We provide a dynamic programming formulation for the combinatorial auction problem, and heuristic algorithms for both the combinatorial auction and the bidding process. An experimental analysis on the whole multi-agent system model is discussed.     

柔性工期下的资源受限项目调度双目标优化研究

在项目调度过程中,活动工期应根据项目截止工期以及资源供给情况进行合理设置,而在传统的资源受限项目调度问题(RCPSP)中,活动的工期往往是已知且固定的,这在一定程度上限制了项目调度的灵活性。多模式下的项目调度方式虽然弥补了这一缺点,但其提供的工期-资源组合种类固定且有限,并不一定能保证包含最优的工期-资源组合。本文将活动工期作为项目调度问题的决策变量,允许其在一定范围内取值。这种柔性工期调度方式虽然增加了项目调度难度,但提高了项目调度灵活性,同时可以起到压缩项目完工时间的作用。为验证柔性工期调度方式对项目工期和成本的影响,本文建立了工期-成本双目标权衡优化模型,设计了两阶段嵌套算法(NSGAⅡ-RS)对其求解,实验证明,柔性工期调度策略是一种鲁棒性较好的项目完工时间压缩策略。     

Finding the shortest path with honey-bee mating optimization algorithm in project management problems with constrained/unconstrained resources

Effective project management requires the development of a realistic plan and a clear communication of the plan from the beginning to the end of the project. The critical path method (CPM) of scheduling is the fundamental tool used to develop and interconnect project plans. Ensuring the integrity and transparency of those schedules is paramount for project success. The complex and discrete nature of the solution domain for such problems causes failing of traditional and gradient-based methods in finding the optimal or even feasible solution in some cases. The difficulties encountered in scheduling construction projects with resource constraints are highlighted by means of a simplified bridge construction problem and a basic masonry construction problem. The honey-bee mating optimization (HBMO) algorithm has been previously adopted to solve mathematical and engineering problems and has proven to be efficient for searching optimal solutions in large-problem domains. This paper presents the HBMO algorithm for scheduling projects with both constrained and unconstrained resources. Results show that the HBMO algorithm is applicable to projects with or without resource constraints. Furthermore, results obtained are promising and compare well with those of well-known heuristic approaches and gradient-based methods.