A multi-objective programming model for scheduling emergency medicine residents

Scheduling emergency medicine residents (EMRs) is a complex task, which considers a large number of rules (often conflicting) related to various aspects such as limits on the number of consecutive work hours, number of day and night shifts that should be worked by each resident, resident staffing requirements according to seniority levels for the day and night shifts, restrictions on the number of consecutive day and night shifts assigned, vacation periods, weekend off requests, and fair distribution of responsibilities among the residents. Emergency rooms (ERs) are stressful workplaces, and in addition shift work is well-known to be more demanding than regular daytime work. For this reason, preparing schedules that suit the working rules for EMRs is especially important for reducing the negative impact on shift workers physiologically, psychologically, and socially. In this paper, we present a goal programming (GP) model that accommodates both hard and soft constraints for a monthly planning horizon. The hard constraints should be adhered to strictly, whereas the soft constraints can be violated when necessary. The relative importance values of the soft constraints have been computed by the analytical hierarchy process (AHP), which are used as coefficients of the deviations from the soft constraints in the objective function. The model has been tested in the ER of a major local university hospital. The main conclusions of the study are that problems of realistic size can be solved quickly and the generated schedules have very high qualities compared to the manually prepared schedules, which require a lot of effort and time from the chief resident who is responsible for this duty.     

Stochastic unit commitment problem

The electric power industry is undergoing restructuring and deregulation. We need to incorporate the uncertainty of electric power demand or power generators into the unit commitment problem. The unit commitment problem is to determine the schedule of power generating units and the generating level of each unit. The objective is to minimize the operational cost which is given by the sum of the fuel cost and the start‐up cost. In this paper we propose a new algorithm for the stochastic unit commitment problem which is based on column generation approach. The algorithm continues adding schedules from the dual solution of the restricted linear master program until the algorithm cannot generate new schedules. The schedule generation problem is solved by the calculation of dynamic programming on the scenario tree.     

连铸-轧制混流生产模式下轧批调度问题的分支-定价算法

研究了连铸——轧制在热装、温装和冷装混流生产模式下的一类新型轧批调度问题.以最小化温装钢坯（热钢锭）缓冷（等待）导致的热能损失和连轧机架切换带来的产能损失为目标,建立了整数规划模型.由于商业优化软件难以在有限时间内直接求得模型的最优解甚至可行解,提出利用Dantzig-Wolfe分解技术将原模型分解为主问题和子问题,采用列生成算法对主问题和子问题进行迭代求解得到原问题的紧下界,最后以列生成算法作为定界机制嵌入分支——定界框架中形成分支——定价算法,执行分支搜索过程以获得整数最优解.本文还从影响分支——定价算法性能的要素出发提出改进策略.针对主问题,提出列生成和拉格朗日松弛混合求解策略来抑制单一列生成算法的尾效应.针对价格子问题,在动态规划算法中提出了基于占优规则和标号下界计算方法来及早消除无效状态空间,加速求解过程.以钢铁企业的实际生产数据和扩展的随机算例进行了数值实验,结果显示所提出改进策略能够突破求解能力的限制,使分支——定价算法在可接受计算时间内求得工业规模问题的最优解.     

Development of a hybrid expert system for nurse shift scheduling

In this article, we discuss the effect of nurse shift job on circadian rhythm, work stress, and some important ergonomics criteria. We also review and compare different nurse shift scheduling methodologies via the criteria of flexibility, consideration of nurse preference, and consideration of ergonomics principles. A hybrid expert system, entitled NURSE-HELP, is developed to facilitate the nurse scheduling process with an emphasis on considering ergonomics criteria. Moreover, the combination of a linear zero-one goal programming and an expert system program reduces the program run time while maintaining the quality of the schedule. The evaluation of the system is done by comparing 18 sets of four-week schedules generated by the head nurses manually and by NURSE-HELP. Concerning the amount of time to generate the schedules, NURSE-HELP averages less than 20 minutes while the head nurses spend about two to four hours. The quality of the schedules is measured by the following four criteria; minimum staff level not satisfied, day off request not granted, backward rotation, and maximum consecutive work periods on the night shift. The results show that NURSE-HELP is superior than the head nurses in preparing schedules, both in terms of time and quality.     

The Variety of Variables in Automated Real-Time Refinement

The refinement calculus is a well-established theory for deriving program code from specifications. Recent research has extended the theory to handle timing requirements, as well as functional ones, and we have developed an interactive programming tool based on these extensions. Through a number of case studies completed using the tool, this paper explains how the tool helps the programmer by supporting the many forms of variables needed in the theory. These include simple state variables as in the untimed calculus, trace variables that model the evolution of properties over time, auxiliary variables that exist only to support formal reasoning, subroutine parameters, and variables shared between parallel processes.     

Weighted sum of maximum regrets in an interval MOLP problem

This paper presents a multiobjective linear programming problem with interval objective function coefficients. Considering the concept of maximum regret, the weighted sum problem of maximum regrets is introduced and its properties are investigated. It is proved that an optimal solution of the weighted sum problem of maximum regrets is at least possibly weakly efficient. Further, the circumstances under which the optimal solution is necessarily efficient (necessarily weakly efficient or possibly efficient) are discussed. Moreover, using a relaxation procedure, an algorithm is proposed, which for a given set of weights finds one feasible solution that minimizes the weighted sum of maximum regrets. A numerical example is provided to illustrate the proposed algorithm.     

A study of one class of NLP problems arising in parametric semi-infinite programming

The paper deals with a nonlinear programming (NLP) problem that depends on a finite number of integers (parameters). This problem has a special form, and arises as an auxiliary problem in study of solutions' properties of parametric semi-infinite programming (SIP) problems with finitely representable compact index sets. Therefore, it is important to provide a deep study of this NLP problem and its properties w.r.t. the values of the parameters. We are especially interested in the case when optimal solutions of the NLP problem satisfy certain properties due to some specific requirements arising in parametric SIP. We establish the values of the parameters for which optimal solutions of the corresponding NLP problem fulfil the needed properties, and suggest an algorithm that determines the right values of the parameters. An example is proposed to illustrate the application of the algorithm.     

An Experimental Study of Algorithms for Weighted Completion Time Scheduling

We consider the total weighted completion time scheduling problem for parallel identical machines and precedence constraints, P| prec|\sum w _i C _i . This important and broad class of problems is known to be NP-hard, even for restricted special cases, and the best known approximation algorithms have worst-case performance that is far from optimal. However, little is known about the experimental behavior of algorithms for the general problem. This paper represents the first attempt to describe and evaluate comprehensively a range of weighted completion time scheduling algorithms. We first describe a family of combinatorial scheduling algorithms that optimally solve the single-machine problem, and show that they can be used to achieve good performance for the multiple-machine problem. These algorithms are efficient and find schedules that are on average within 1.5\percent of optimal over a large synthetic benchmark consisting of trees, chains, and instances with no precedence constraints. We then present several ways to create feasible schedules from nonintegral solutions to a new linear programming relaxation for the multiple-machine problem. The best of these linear programming-based approaches finds schedules that are within 0.2\percent of optimal over our benchmark. Finally, we describe how the scheduling phase in profile-based program compilation can be expressed as a weighted completion time scheduling problem and apply our algorithms to a set of instances extracted from the SPECint95 compiler benchmark. For these instances with arbitrary precedence constraints, the best linear programming-based approach finds optimal solutions in 78\percent of cases. Our results demonstrate that careful experimentation can help lead the way to high quality algorithms, even for difficult optimization problems. Received October 30, 1998; revised March 28, 2001.     

Scheduling the professional Ecuadorian football league by integer programming

A sports schedule sets the dates and venues of games among teams in a sports league. Constructing a sports schedule is a highly restrictive problem. The schedule must meet constraints due to regulations of a particular sports league federation and it must guarantee the participation of all teams on equal terms. Moreover, economic benefits of the teams and other agents involved in this activity are expected. Until 2011, the Ecuadorian football federation (FEF) had developed schedules for their professional football championship manually. In early 2011, the authors presented to the FEF authorities evidence that the use of mathematical programming to create feasible sports schedules could easily exceed the benefits obtained by the empirical method. Under this premise, this work presents an integer programming formulation, solved to optimality, for scheduling the professional football league in Ecuador, and also a heuristic approach based on three-phases for its solution. The schedules obtained met the expectations of the FEF and one of them was adopted as the official schedule for the 2012 edition of the Ecuadorian professional football championship.     

Rostering in a rail passenger carrier

In this paper we present an applied study, commissioned by the regional rail passenger carrier EuskoTren, into how the annual workload of drivers can be allocated in an egalitarian fashion. The allocation must meet the constraints arising from working conditions and the preferences of employees, as reflected in collective bargaining agreements. The workload varies over the five periods, into which the year is divided, and according to the day of the week. Moreover, not all morning, evening and night shifts are of equal duration. Reduced services on public holidays are also considered. The solution to the problem proposed is obtained in four linked steps, at each of which a binary programming problem is solved using commercial software. Step one is to build five lists of weekly multi-shift patterns, two of them rotating, that contain all the shifts in the week. Step two consists of the partially rotating annual assignment of patterns to drivers, step three involves the extraction of shifts by reduction of services on public holidays, and step four incorporates the durations in hours into the shifts already assigned. The final solution obtained is quite satisfactory: all drivers are assigned a similar number of morning, evening and night shifts and Sundays off, and they work practically the same number of days and hours per year. The results obtained, the adaptability of the system to new requirements and the computation time used are fully satisfactory to the firm, which has decided to implement the model.     

Branch and price for covering shipments in a logistic distribution network with a fleet of aircraft

We consider the problem of covering a set of shipments in a logistic distribution network with a fleet of aircraft. The aim is to cover as many shipments as possible, while also minimizing the number of aircraft utilized for that purpose. We develop an integer programming model and a branch and price solution algorithm for this problem. The proposed methodology utilizes a master problem that covers the maximum possible number of shipments using a given set of aircraft-routes, and a column generation subproblem that generates cost-effective aircraft-routes which are fed into the master problem. We describe the proposed methodology, illustrating how it can be modified in order to accommodate several problem extensions. We also investigate how its efficiency is affected by various key design parameters. We conclude with extensive experimental results demonstrating its computational performance.     

A new heuristic algorithm for the operating room scheduling problem

Due to the great importance of operating rooms in hospitals, this paper studies an operating room scheduling problem with open scheduling strategy. According to this strategy, no time slot is reserved for a particular surgeon. The surgeons can use all available time slots. Based on Fei et al.’s model which is considered to be close to reality, we develop a heuristic algorithm to solve it. The idea of this heuristic algorithm is from dynamic programming by aggregating states to avoid the explosion of the number of states. The objective of this paper is to design an operating program to maximize the operating rooms’ use efficiency and minimize the overtime cost. Computational results show that our algorithm is efficient, especially for large size instances where our algorithm always finds feasible solutions while the algorithm of Fei et al. does not.     

一种改进的遗传规划算法

遗传规划的实质是用广义的层次化计算机程序描述问题．比较适合于求解一类由于各种不确定因素导致的复杂非线性问题。该文采用了一种改进的遗传规划算法,建立了相应的预测模型,将其与Weka里的GP算法在标准数据集上进行对比测试,结果表明该改进的遗传规划算法是有效的、可行的。     

A dynamic convexized method for nonconvex mixed integer nonlinear programming

We consider in this paper the nonconvex mixed-integer nonlinear programming problem. We present a mixed local search method to find a local minimizer of an unconstrained nonconvex mixed-integer nonlinear programming problem. Then an auxiliary function which has the same global minimizers and the same global minimal value as the original problem is constructed. Minimization of the auxiliary function using our local search method can escape successfully from previously converged local minimizers by taking increasing values of parameters. For the constrained nonconvex mixed-integer nonlinear programming problem, we develop a penalty based method to convert the problem into an unconstrained one, and then use the above method to solve the later problem. Numerical experiments and comparisons on a set of MINLP benchmark problems show the effectiveness of the proposed algorithm.     

考虑胜任力水平的研发项目群人力资源调度

在资源受限项目调度问题中,将可更新资源进一步拓展为具有胜任力差异的人力资源,建立考虑胜任力差异的人力资源受限项目调度问题模型,该模型是对传统多模式资源约束项目调度问题（MRCPSP）更接近研发项目群实际的扩展。提出了衡量人员胜任力的参数及估算公式,以多项目总工期和总成本最小化为双目标,建立相应的数学优化模型。按双目标重要性排序,依次对工期最优及成本最优的单目标优化问题求解。根据模型的约束条件将多项目初始网络图转化为几种单项目初始网络图,利用枚举算法给出满足约束条件的可行解集,再设计基于动态规划思想的算法进行分阶段寻优。数值实验表明,考虑了胜任力差异的数学优化模型在求解质量方面具有良好性能。     

A column generation heuristic for a dynamic generalized assignment problem

This paper studies the dynamic generalized assignment problem (DGAP) which extends the well-known generalized assignment problem by considering a discretized time horizon and by associating a starting time and a finishing time with each task. Additional constraints related to warehouse and yard management applications are also considered. Three linear integer programming formulations of the problem are introduced. The strongest one models the problem as an origin–destination integer multi-commodity flow problem with side constraints. This model can be solved quickly for instances of small to moderate size. However, because of its computer memory requirements, it becomes impractical for larger instances. Hence, a column generation algorithm is used to compute lower bounds by solving the linear program (LP) relaxation of the problem. This column generation algorithm is also embedded in a heuristic aimed at finding feasible integer solutions. Computational experiments on large-scale instances show the effectiveness of the proposed approach.     

A discrete time exact solution approach for a complex hybrid flow-shop scheduling problem with limited-wait constraints

We study a real-world complex hybrid flow-shop scheduling problem arising from a bio-process industry. There are a variety of constraints to be taken into account, in particular zero intermediate capacity and limited waiting time between processing stages. We propose an exact solution approach for this optimization problem, based on a discrete time representation and a mixed-integer linear programming formulation. The proposed solution algorithm makes use of a new family of valid inequalities exploiting the fact that a limited waiting time is imposed on jobs between two successive production stages. The results of our computational experiments confirm that the proposed method produces good feasible schedules for industrial instances.     

An Approach to Platform Independent Real-Time Programming: (2) Practical Application

In a previously published companion paper a method for extending programming languages with timing constructs was proposed. It was shown that the extension enables the construction of real-time programs that can be proven correct independently of the properties of the machine that is used for their execution. It also yields a strict division of system construction into two phases: (1) a platform-independent programming phase that includes the expression of timing requirements, and (2) an implementation phase where all platform dependencies are addressed. In this second paper the approach is illustrated using an example problem often quoted in the literature: the mine-pump system. The two mentioned phases are described in detail for this example. First, a program is obtained in a systematic way. Then, realizations of the program under various schemes for distribution and scheduling are considered and analyzed. A comparison with other approaches to real-time programming is given.     

Minimizing costs in round robin tournaments with place constraints

In this paper we consider a general sports league scheduling problem and propose solution algorithms for it. The objective is to find a feasible schedule for a round robin tournament with minimum number of breaks and minimum total costs where additionally place constraints are taken into account. We present a “first-break, then-schedule” approach which uses an enumerative procedure to generate home-away patterns and integer programming for finding corresponding schedules. Computational results are presented for leagues with up to 14 teams.