Solving the multi-objective nurse scheduling problem with a weighted cost function

The primary objective of the nurse scheduling problem is to ensure there are sufficient nurses on each shift. There are also a number of secondary objectives designed to make the schedule more pleasant. Neighbourhood search implementations use a weighted cost function with the weights dependent on the importance of each objective. Setting the weights on binding constraints so they are satisfied but still allow the search to find good solutions is difficult. This paper compares two methods for overcoming this problem, SAWing and Noising with simulated annealing and demonstrates that Noising produces better schedules.     

Complexity of flow shop scheduling problems with transportation constraints

In most manufacturing and distribution systems, semi-finished jobs are transferred from one processing facility to another by transporters such as Automated Guided Vehicles, robots and conveyors, and finished jobs are delivered to warehouses or customers by vehicles such as trucks.This paper investigates two-machine flow shop scheduling problems taking transportation into account. The finished jobs are transferred from the processing facility and delivered to customers by truck. Both transportation capacity and transportation times are explicitly taken into account in these models. We study the class of flow shop problems by analysing their complexity. For the makespan objective function, we prove that this problem is strongly NP-hard when the capacity of a truck is limited to two or three parts with an unlimited buffer at the output of the each machine. This problem with additional constraints, such as blocking, is also proven to be strongly NP-hard.     

Analytical approximations to predict performance measures of markovian type manufacturing systems with job failures and parallel processing

Manufacturing or service systems with multiple product classes, job circulation due to random failures, resources shared between product classes, and some portions of the manufacturing or assembly carried in series and the rest in parallel are commonly observed in real-life. The web server assembly is one such manufacturing system which exhibits the above characteristics. Predicting the performance measures of these manufacturing systems is not an easy task. The primary objective of this research was to propose analytical approximations to predict the flow times of the manufacturing systems, with the above characteristics, and evaluate its accuracy. The manufacturing system is represented as a network of queues. The parametric decomposition approach is used to develop analytical approximations for a system with arrival and service rates from a Markovian distribution. The results from the analytical approximations are compared to simulation models. In order to bridge the gap in error, correction terms were developed through regression modeling. The experimental study conducted indicates that the analytical approximations along with the correction terms can serve as a good estimate for the flow times of the manufacturing systems with the above characteristics.     

Capacitated emergency facility siting with multiple levels of backup

In many service systems, the primary objective is to provide continuous service and/or service within a prespecified time interval. In the public sector, emergency service systems fit into this category. In the private sector, systems providing repair service to critical production facilities and computers constitute another example. In these systems, the concept of multiple service facilities providing backup to each other becomes an important element in the design process. In this paper, we study the capacitated facility siting problem with multiple levels of backup coverage. The problem is formulated as a mathematical program; an efficient solution procedure is developed and computational experiments are reported.     

Optimising key performance indicator adherence with application to emergency department congestion

Many operational queueing systems must adhere to systems of Key Performance Indicators (KPIs), each comprising a waiting time limit and a level of compliance specifying the minimal fraction of customers that must meet the standard. KPIs are frequently employed as measures of system performance in health care settings. The primary flaw with KPIs is that they represent a system of constraints with no objective function. KPIs say nothing about customers who exceed their limit, so long as such occurrences are sufficiently rare, when in fact customers who miss their time limit in a health care setting are of greater importance, not lesser. We address this flaw by minimising the mean number of customers present who have exceeded their respective limits; we consider also weighted averages of the numbers in excess for each class. We then show that one logical service discipline to achieve this goal is the Accumulating Priority Queueing (APQ) discipline. We carry out numerical examples to investigate the utility of our method. We then apply the optimisation approach to the case of an Emergency Department in Southern Ontario, Canada.     

Monotone Approximations of Minimum and Maximum Functions and Multi-objective Problems

In this paper the problem of accomplishing multiple objectives by a number of agents represented as dynamic systems is considered. Each agent is assumed to have a goal which is to accomplish one or more objectives where each objective is mathematically formulated using an appropriate objective function. Sufficient conditions for accomplishing objectives are derived using particular convergent approximations of minimum and maximum functions depending on the formulation of the goals and objectives. These approximations are differentiable functions and they monotonically converge to the corresponding minimum or maximum function. Finally, an illustrative pursuit-evasion game example with two evaders and two pursuers is provided.     

A multi-depot period vehicle routing problem arising in the utilities sector

This paper considers the resource planning problem of a utility company that provides preventive maintenance services to a set of customers using a fleet of depot-based mobile gangs. The problem is to determine the boundaries of the geographic areas served by each depot, the list of customers visited each day and the routes followed by the gangs. The objective is to provide improved customer service at minimum operating cost subject to constraints on frequency of visits, service time requirements, customer preferences for visiting on particular days and other routing constraints. The problem is solved as a Multi-Depot Period Vehicle Routing Problem (MDPVRP). The computational implementation of the complete planning model is described with reference to a pilot study and results are presented. The solution algorithm is used to construct cost-service trade-off curves for all depots so that management can evaluate the impact of different customer service levels on total routing costs.     

Saddle Points and Pareto Points in Multiple Objective Programming

In this paper relationships between Pareto points and saddle points are studied in convex and nonconvex multiple objective programming. The analysis is based on partitioning the index sets of objectives and constraints and splitting the original problem into subproblems having a special structure. The results are based on scalarizations of multiple objective programs and related linear and augmented Lagrangian functions. In the nonconvex case, a saddle point characterization of Pareto points is possible under assumptions that guarantee existence of Pareto points and stability conditions of single objective problems. Essentially, these conditions are not stronger than those in analogous results for single objective programming.This research was partially supported by ONR Grant N00014-97-1-784AMS Subject Classification: 90C29, 90C26     

Optimal Release Times in Single-Stage Manufacturing Systems with Blocking: Optimal Control Perspective

This paper concerns a due-date matching problem in a single-stage manufacturing system. Given a finite sequence of jobs and their service order, and given the delivery due date of each job, the problem is to choose the jobs release (arrival) times so as to match as closely as possible their completion times to their respective due dates. The system is modelled as a deterministic single-server FIFO queue with an output buffer for storing jobs whose service is completed prior to their due dates. The output buffer has a finite capacity; when it is full, the server is being blocked. Associated with each job there is a convex cost function penalizing its earliness as well as tardiness. The due-date matching problem is cast as an optimal control problem, whose objective is to minimize the sum of the above cost functions by the choice of the jobs arrival (release) times. Time-box upper-bound and lower-bound constraints are imposed on the jobs output (delivery) times. The optimal-control setting brings to bear on the development of fast and efficient algorithms having intuitive geometric appeal and potential for online implementation.Communicated by W. B. GongResearch supported in part by the National Science Foundation under Grant ECS-9979693 and by the Georgia Tech Manufacturing Research Center under Grant B01-D06.     

Capacity planning in networks of queues with manufacturing applications

This paper addresses capacity planning in systems that can be modeled as a network of queues. More specifically, we present an optimization model and solution methods for the minimum cost selection of capacity at each node in the network such that a set of system performance constraints is satisfied. Capacity is controlled through the mean service rate at each node. To illustrate the approach and how queueing theory can be used to measure system performance, we discuss a manufacturing model that includes upper limits on product throughput times and work-in-process in the system. Methods for solving capacity planning problems with continuous and discrete capacity options are discussed. We focus primarily on the discrete case with a concave cost function, allowing fixed charges and costs exhibiting economies of scale with respect to capacity to be handled.     

Optimal resource allocation for multiqueue systems with a shared server pool

We study optimal allocation of servers for a system with multiple service facilities and with a shared pool of servers. Each service facility poses a constraint on the maximum expected sojourn time of a job. A central decision maker can dynamically allocate servers to each facility, where adding more servers results in faster processing speeds but against higher utilization costs. The objective is to dynamically allocate the servers over the different facilities such that the sojourn-time constraints are met at minimal costs. This situation occurs frequently in practice, for example, in Grid systems for real-time image processing (iris scans, fingerprints). We model this problem as a Markov decision process and derive structural properties of the relative value function. These properties, which are hard to derive for multidimensional systems, give a full characterization of the optimal policy. We demonstrate the effectiveness of these policies by extensive numerical experiments.     

Endogenous optimization fisheries models

This paper deals with a special class of fisheries models referred to as endogenous optimization models. The distinctive feature of these models is that behaviour of the agents in the model is not predetermined by exogenous behavioural rules. In endogenous optimization models, the model agents are merely furnished with objectives such as profit or utility maximization. Given these objectives and the various constraints determined by the state of the model at each point of time, the agents solve their maximization problem. The corresponding values of their control variables then constitute their behaviour.Having generated individual agents' behaviour by endogenous optimization, summing over agents yields aggregate behaviour. Aggregate behaviour must conform with the overall constraints of the model, be they physical or otherwise. Within the market system, individual behaviour or rather plans are made compatible via changes in relative prices. Therefore, outside equilibrium, behavioural plans must be repeatedly modified to become mutually compatible. This implies iteratively solving the maximization problem of a number of different agents. Endogenous optimization models therefore tend to be computationally very demanding.Clearly, the basic principles of endogenous optimization are just as applicable to any model involving maximizing agents.     

A characterization of weakly efficient points

In this paper, we study a characterization of weakly efficient solutions of Multiobjective Optimization Problems (MOPs). We find that, under some quasiconvex conditions of the objective functions in a convex set of constraints, weakly efficient solutions of an MOP can be characterized as an optimal solution to a scalar constraint problem, in which one of the objectives is optimized and the remaining objectives are set up as constraints. This characterization is much less restrictive than those found in the literature up to now.Corresponding author.     

A regularized decomposition method for minimizing a sum of polyhedral functions

A problem of minimizing a sum of many convex piecewise-linear functions is considered. In view of applications to two-stage linear programming, where objectives are marginal values of lower level problems, it is assumed that domains of objectives may be proper polyhedral subsets of the space of decision variables and are defined by piecewise-linear induced feasibility constraints. We propose a new decomposition method that may start from an arbitrary point and simultaneously processes objective and feasibility cuts for each component. The master program is augmented with a quadratic regularizing term and comprises an a priori bounded number of cuts. The method goes through nonbasic points, in general, and is finitely convergent without any nondegeneracy assumptions. Next, we present a special technique for solving the regularized master problem that uses an active set strategy and QR factorization and exploits the structure of the master. Finally, some numerical evidence is given.On leave from Instytut Automatyki, Politechnika Warszawska, Poland.     

考虑加工速率相互干扰的平行机调度最优策略研究

随着智能互联网的应用深入、个性化消费时代的来临,制造服务企业开始注重利用网络平台为客户提供个性化的定制服务,在此过程中派生出了产品设计师可与多名客户在线同步交互的一种新型服务模式。本文根据设计师服务效率受并行服务客户数量影响的特征,将问题刻画为机器处理速度相互影响的一类平行机调度模型,以最小化总完工时间为优化目标,研究设计最优调度方案。首先,对于只有两名设计师且各自同时处理最多两个任务的情形,提出了改进的SPT调度规则,运用归纳法证明了该规则可以生成最优加工方案。其次,对改进的SPT规则进行任务分配方式的适当松驰以便更加易于操作,并证明松驰后的新分配方案保持了解的最优性。最后,将相关结论推广至多名设计师的一般情形。上述研究为个性化在线定制服务模式下的有效调度策略制定提供了良好的理论支撑。     

A Timetabling Problem in which Clashes are Inevitable

This paper is concerned with a university timetabling problem in which some clashes are unavoidable if the weekly lecture requirements are to be scheduled in the available time-slots. The solution needs to satisfy a number of different objectives. Most of these are achieved by imposing a series of constraints, and the problem is reduced to that of minimizing the single objective of student disappointment. Three models—graph colouring, set partitioning and simulated annealing—are suggested, and the advantages and disadvantages of using each of these to find a satisfactory solution are discussed.     

Covering and connectivity constraints in loop-based formulation of material flow network design in facility layout

The shortest loop covering at least one edge of each workcenter in a manufacturing facility layout is an instance of the generalized traveling salesman problem. The optimal solution to this problem is a promising design for non-vehicle-based material handling, typical of most types of conveyors and power-and-free systems, where the length of the path is the main driver of the total investment costs. The loop formulation is usually embedded within a larger problem of the concurrent design of the loop and the input/output stations for vehicle-based material handling typical of automatically guided vehicles and autonomous delivery robots. In these systems, it is not the length, but the total flow of the loaded and empty vehicles that drives the objective function. It has been shown that the shortest loop provides an effective heuristic scheme to achieve prosperous and robust solutions for the concurrent design of the loop and input/output stations. We review and compare covering constraints formulations, provide new insight into connectivity constraints, improve the model formulation and its solution procedure, and report computational results.     

A lexicographic approach to bi-objective scheduling of single-period orders in make-to-order manufacturing

This paper presents a lexicographic approach and integer programming formulations for a dual-objective, long-term production scheduling in make-to-order manufacturing environment. The problem objective is to assign single-period customer orders for various product types to planning periods to complete all the orders with minimum number of tardy orders as a primary criterion and to level the aggregate production or the total capacity utilization over a planning horizon as a secondary criterion. Each order must be completed during one planning period. The basic integer programming formulation has been strengthened by the addition of some cutting constraints derived by relating the demand on required capacity to available capacity for each subset of orders with the same due date. The approach has been applied to optimize production schedules in a flexible flowshop made up of several processing stages in series, with identical, parallel machines, and an output buffer of limited capacity for holding completed products before delivery to the customers. Numerical examples modeled after a real-world make-to-order flexible assembly line in the electronics industry are provided and some computational results are reported.     

Decomposition of the fuzzy parametric space in multiobjective nonlinear programming problems

This paper deals with a method for decomposing the fuzzy parametric space in multiobjective nonlinear programming problems using the generalized Tchebycheff norm. This approach is simpler than the corresponding one using the nonnegative weighted sum of objectives. Also, several results are introduced which relate two fuzzy programs with each other, one with fuzzy parameters in the constraints and the other with fuzzy parameters in both objective functions and constraints. These fuzzy parameters are characterized by fuzzy numbers. The existing results concerning the decomposition of parametric space in multiobjective convex programs using the generalized Tchebycheff norm are reformulated to study under the concept of α-pareto optimality. Such results make the study of the first type of problems rather simple. Three illustrated examples are presented in the paper which clarify the developed theory.     

Characterizing the performance of process flexibility structures

The objective is to identify preferred flexibility structures in service or manufacturing systems, when demand is random and capacity is finite. Considering a network flow type model as the basis of the analysis, general structural properties of flexibility design pertaining to the marginal values of flexibility and capacity are identified.