A comparison of utility-oriented algorithms for scheduling parallel tasks in multi-cluster grid

Scheduling parallel tasks in multi-cluster grid can be seen as two interdependent problems: cluster allocation and scheduling parallel task on the allocated cluster. In this paper both rigid and moldable parallel tasks are considered. We propose a theoretical model of utility-oriented parallel task scheduling in multi-cluster grid with advance reservations. On the basis of the model we present an approximation algorithm, a repair strategy based genetic algorithm and greedy heuristics MaxMax, T-Sufferage and R-Sufferage to solve the two interdependent problems. We compare the performance of these algorithms in aspect of utility optimality and timing results. Simulation results show on average the (1+α)-approximation algorithm achieves the best trade-off between utility optimality and timing. Genetic algorithm could achieve better utility than greedy heuristics and approximate algorithm at expensive time cost. Greedy heuristics do not perform equally well when adapted to different utility functions while the approximation algorithm shows its intrinsic stable performance.     

Revenue management for outpatient appointments: joint capacity control and overbooking with class-dependent no-shows

Outpatient appointment scheduling balances efficiency with access to healthcare services, yet appointment no-shows, cancellations, and delay are significant barriers to effective healthcare delivery. Patients with longer appointment delay often waste appointments more frequently, prompting a need for greater flexibility in appointment allocation. We present a joint capacity control and overbooking model where a clinic maximizes profits by controlling bookings from two sequential patient classes with different no-show rates. When booking advance requests, the clinic must balance high no-show probability with the probability of subsequent requests at lower waste rates. We show the optimal policy is computationally intensive to derive; therefore, we develop bounds and approximations which we compare via numerical study with the optimal policy as well as policies from practice and previous literature. We find the optimal policy increases profits 17.8% over first-come-first-serve allocation. We develop a simple policy which performs 0.3% below optimal on average. While pure open access can achieve optimality, it performs 23.0% below optimal on average.     

Nonlinear costs and optimal fleet capacity in deterministic and stochastic fisheries

This paper presents a bioeconomic model for determining optimal fisheries investment strategies in both deterministic and stochastic environments. An analytic approach is followed; formulas are derived to describe the effects of depreciation, discounting, and randomness on the optimal fleet capacity, for the general case of nonlinear fishing costs as well as the less complex linear case. To accomplish this, fish stock dynamics are simplified, by assuming that current stock sizes are independent of past escapements. The extremity of this assumption is lessened through the use of an “opportunity cost of escapement” penalty function to account subjectively for the de facto cost of low escapements.     

Optimal design of protein production plants with time and size factor process models

In this work we propose an optimization model for the design of a biotechnological multiproduct batch plant. A first level of detail posynomial model is constructed for each unit, as well as decisions regarding the structural optimization of the plant. A particular feature of this model is that it contains composite units in which semicontinuous items operate on the material contained by batch items. This occurs in the purification steps, in particular with the microfilters operating between retentate and permeate vessels, and with the homogenizer and ultrafilters operating on the material contained in a batch holding vessel. Also, the unit models rely on batch operating time expressions that depend on both the batch size and the size of semicontinuous items. The model takes into account all of the available options to increase the efficiency of the batch plant design: unit duplication in-phase and out-of-phase and intermediate storage tanks. The resulting mathematical model for the minimization of the plant capital cost is a mixed integer non-linear program (MINLP), which is solved to global optimality with an implementation of the outer approximation/ equality relaxation/ augmented penalty (OA/ER/AP) method. A plant that produces four recombinant proteins in eight processing stages is used to illustrate the proposed approach. An interesting feature of this example is that it represents an attempt to standardize a plant for the production of both therapeutic and nontherapeutic proteins; the model applied is generic and can thus be applied to any such modular plant. Results indicate that the best solution in terms of minimal capital cost contains no units in parallel and with intermediate storage tank allocation.     

Effect of reconfiguration costs on planning for capacity scalability in reconfigurable manufacturing systems

In a globally competitive market for products, manufacturers are faced with an increasing need to improve their flexibility, reliability, and responsiveness to meet the demands of their customers. Reconfigurable manufacturing systems (RMS) have become an important manufacturing paradigm, because they broadly encompass the ability to react efficiently to this environment by providing the exact capacity and functionality needed when needed. This paper studies how such new systems can manage their capacity scalability planning in a cost effective manner. An approach for modeling capacity scalability planning is proposed. The development of the model is based on set theory and the regeneration point theorem which is mapped to the reconfigurable manufacturing paradigm as the capacity scalability points of that system. The cost function of the model incorporates both the physical capacity cost based on capacity size and costs associated with the reconfiguration process which referred to as the scalability penalty cost and scalability effort cost. A dynamic programming (DP) approach is manipulated for the development of optimal capacity scalability plans. The effect of the reconfiguration costs on the capacity scalability planning horizon and overall cost is investigated. The results showed the relation between deciding on the optimal capacity scalability planning horizon and the different reconfiguration costs. Results also highlighted the fact that decreasing costs of reconfiguration will lead to cost effective implementation of reconfigurable manufacturing systems.     

A Generic Model to Solve Tactical Planning Problems in Flexible Manufacturing Systems

This paper is an attempt to develop a generic modeling framework that addresses tactical planning problems of flexible manufacturing systems in a coherent manner. We propose a generic 0-1 mixed integer programming formulation, that integrates batching, loading, and routing problems with their critical aspects related to a system's performance. For this purpose, a thorough analysis is made to determine and relate system components, their attributes, and alternatives together with performance measures specific to tactical planning. This provided the justification to support our argument about generality of the model. A linear programming formulation is provided to approximate the mixed integer formulation proposed so as to overcome the problem's combinatorial complexity. The potential capability of the linear approximation proposed also is demonstrated via a small set of test problems.     

Bayesian Nonparametric Modeling Using Mixtures of Triangular Distributions

Nonparametric modeling is an indispensable tool in many applications and its formulation in an hierarchical Bayesian context, using the entire posterior distribution rather than particular expectations, increases its flexibility. In this article, the focus is on nonparametric estimation through a mixture of triangular distributions. The optimality of this methodology is addressed and bounds on the accuracy of this approximation are derived. Although our approach is more widely applicable, we focus for simplicity on estimation of a monotone nondecreasing regression on [0, 1] with additive error, effectively approximating the function of interest by a function having a piecewise linear derivative. Computationally accessible methods of estimation are described through an amalgamation of existing Markov chain Monte Carlo algorithms. Simulations and examples illustrate the approach.     

Deterministic global optimization algorithm based on outer approximation for the parameter estima- tion of nonlinear dynamic biological systems

ABSTRACT: BACKGROUND: The estimation of parameter values for mathematical models of biological systems is an optimization problem that is particularly challenging due to the nonlinearities involved. One major difficulty is the existence of multiple minima in which standard optimization methods may fall during the search. Deterministic global optimization methods overcome this limitation, ensuring convergence to the global optimum within a desired tolerance. Global optimization techniques are typically classified into stochastic and deterministic. The former typically lead to lower CPU times but offer no guarantee of convergence to the global minimum in a finite number of iterations. In contrast, deterministic methods provide solutions of a given quality (i.e., optimality gap), but tend to lead to large computational burdens. RESULTS: This work presents a deterministic outer approximation-based algorithm for the global optimization of dynamic problems arising in the parameter estimation of models of biological systems. Our approach, which offers a theoretical guarantee of convergence to the global minimum, reformulating the set of ordinary differential equations into an equivalent set of algebraic equations through the use of orthogonal collocation methods, giving rise to a nonconvex nonlinear programming (NLP) problem. This nonconvex NLP is decomposed into two hierarchical levels: a master mixed-integer linear programming problem (MILP) that provides a rigorous lower bound on the optimal solution, and a reduced-space slave NLP that yields an upper bound. The algorithm iterates between these two levels until a termination criterion is satisfied. CONCLUSION: The capabilities of our approach were tested in two benchmark problems, in which the performance of our algorithm was compared with that of the commercial global optimization package BARON. The proposed strategy produced near optimal solutions (i.e., within a desired tolerance) in a fraction of the CPU time required by BARON.     

A stochastic approach to predator-prey models

A deterministic investigation of a linear differential equation system which describes predator vs prey behavior as a function of equilibrium densities and reproductive rates is given. A more realistic structure of this model in a stochastic framework is presented. The reproductive rates and initial population sizes are considered to be random variables and their probabilistic behavior characterized by various joint probability distributions. The deterministic behaviors of the prey and predator species as functions of time are compared with the mean behaviors in the stochastic model.     

Variable Selection for Semiparametric Mixed Models in Longitudinal Studies

Summary .  We propose a double-penalized likelihood approach for simultaneous model selection and estimation in semiparametric mixed models for longitudinal data. Two types of penalties are jointly imposed on the ordinary log-likelihood: the roughness penalty on the nonparametric baseline function and a nonconcave shrinkage penalty on linear coefficients to achieve model sparsity. Compared to existing estimation equation based approaches, our procedure provides valid inference for data with missing at random, and will be more efficient if the specified model is correct. Another advantage of the new procedure is its easy computation for both regression components and variance parameters. We show that the double-penalized problem can be conveniently reformulated into a linear mixed model framework, so that existing software can be directly used to implement our method. For the purpose of model inference, we derive both frequentist and Bayesian variance estimation for estimated parametric and nonparametric components. Simulation is used to evaluate and compare the performance of our method to the existing ones. We then apply the new method to a real data set from a lactation study.     

Algorithmic and complexity results for decompositions of biological networks into monotone subsystems

A useful approach to the mathematical analysis of large-scale biological networks is based upon their decompositions into monotone dynamical systems. This paper deals with two computational problems associated to finding decompositions which are optimal in an appropriate sense. In graph-theoretic language, the problems can be recast in terms of maximal sign-consistent subgraphs. The theoretical results include polynomial-time approximation algorithms as well as constant-ratio inapproximability results. One of the algorithms, which has a worst-case guarantee of 87.9% from optimality, is based on the semidefinite programming relaxation approach of Goemans-Williamson [Goemans, M., Williamson, D., 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42 (6), 1115-1145]. The algorithm was implemented and tested on a Drosophila segmentation network and an Epidermal Growth Factor Receptor pathway model, and it was found to perform close to optimally.     

Optimal harvesting of a logistic population in an environment with stochastic jumps

Dynamic programming is employed to examine the effects of large, sudden changes in population size on the optimal harvest strategy of an exploited resource population. These changes are either adverse or favorable and are assumed to occur at times of events of a Poisson process. The amplitude of these jumps is assumed to be density independent. In between the jumps the population is assumed to grow logistically. The Bellman equation for the optimal discounted present value is solved numerically and the optimal feedback control computed for the random jump model. The results are compared to the corresponding results for the quasi-deterministic approximation. In addition, the sensitivity of the results to the discount rate, the total jump rate and the quadratic cost factor is investigated. The optimal results are most strongly sensitive to the rate of stochastic jumps and to the quadratic cost factor to a lesser extent when the deterministic bioeconomic parameters are taken from aggregate antarctic pelagic whaling data.Research supported in part by the National Science Foundation under grants MCS 81-01698 and MCS 83-00562.     

A Jump-Growth Model for Predator–Prey Dynamics: Derivation and Application to Marine Ecosystems

This paper investigates the dynamics of biomass in a marine ecosystem. A stochastic process is defined in which organisms undergo jumps in body size as they catch and eat smaller organisms. Using a systematic expansion of the master equation, we derive a deterministic equation for the macroscopic dynamics, which we call the deterministic jump-growth equation, and a linear Fokker–Planck equation for the stochastic fluctuations. The McKendrick–von Foerster equation, used in previous studies, is shown to be a first-order approximation, appropriate in equilibrium systems where predators are much larger than their prey. The model has a power-law steady state consistent with the approximate constancy of mass density in logarithmic intervals of body mass often observed in marine ecosystems. The behaviours of the stochastic process, the deterministic jump-growth equation, and the McKendrick–von Foerster equation are compared using numerical methods. The numerical analysis shows two classes of attractors: steady states and travelling waves.     

The frequency-dependent Wright–Fisher model: diffusive and non-diffusive approximations

We study a class of processes that are akin to the Wright–Fisher model, with transition probabilities weighted in terms of the frequency-dependent fitness of the population types. By considering an approximate weak formulation of the discrete problem, we are able to derive a corresponding continuous weak formulation for the probability density. Therefore, we obtain a family of partial differential equations for the evolution of the probability density, and which will be an approximation of the discrete process in the joint large population, small time-steps and weak selection limit. If the fitness functions are sufficiently regular, we can recast the weak formulation in a more standard formulation, without any boundary conditions, but supplemented by a number of conservation laws. The equations in this family can be purely diffusive, purely hyperbolic or of convection–diffusion type, with frequency dependent convection. The particular outcome will depend on the assumed scalings. The diffusive equations are of the degenerate type; using a duality approach, we also obtain a frequency dependent version of the Kimura equation without any further assumptions. We also show that the convective approximation is related to the replicator dynamics and provide some estimate of how accurate is the convective approximation, with respect to the convective-diffusion approximation. In particular, we show that the mode, but not the expected value, of the probability distribution is modelled by the replicator dynamics. Some numerical simulations that illustrate the results are also presented.     

Modeling order assignment for semiconductor assembly hierarchical outsourcing and developing the decision support system

Outsourcing has become increasingly important in supply chain management. As the semiconductor industry is capital-intensive, semiconductor manufacturing companies focus on wafer fabrication as their core competence and outsource assembly and testing to a number of specialized vendors. The involved decision-making has multiple objectives such as (1) minimizing the number of delayed orders, (2) minimizing the allocation ratio differences, (3) minimizing the assembly cost, and (4) minimizing the product changeover times. To meet these objectives in practice, this study proposes an approach that employs mixed integer linear programming and goal programming to integrate multiple objectives and operational feasibility by considering mass orders, order fulfillment, capacity limits, logistics timetables, and a rolling mechanism in a real setting. Furthermore, we developed an order assignment decision support system embedded with the proposed approach for assigning assembly outsourcing orders and validated the system in a semiconductor company in Taiwan. The results have shown the practical viability of the proposed approach in terms of decision quality and computational efficiency. This study concludes with empirical findings and a discussion of future research directions.     

A Joint Modeling Approach for Longitudinal Data with Informative Observation Times and a Terminal Event

In this article, we propose a new joint modeling approach for the analysis of longitudinal data with informative observation times and a dependent terminal event. We specify a semiparametric mixed effects model for the longitudinal process, a proportional rate frailty model for the observation process, and a proportional hazards frailty model for the terminal event. The association among the three related processes is modeled via two latent variables. Estimating equation approaches are developed for parameter estimation, and the asymptotic properties of the proposed estimators are established. The finite sample performance of the proposed estimators is examined through simulation studies, and an application to a medical cost study of chronic heart failure patients is illustrated.     

Penalized estimating equations

Penalty models--such as the ridge estimator, the Stein estimator, the bridge estimator, and the Lasso-have been proposed to deal with collinearity in regressions. The Lasso, for instance, has been applied to linear models, logistic regressions, Cox proportional hazard models, and neural networks. This article considers the bridge penalty model with penalty sigma(j)/beta(j)/gamma for estimating equations in general and applies this penalty model to the generalized estimating equations (GEE) in longitudinal studies. The lack of joint likelihood in the GEE is overcome by the penalized estimating equations, in which no joint likelihood is required. The asymptotic results for the penalty estimator are provided. It is demonstrated, with a simulation and an application, that the penalized GEE potentially improves the performance of the GEE estimator, and enjoys the same properties as linear penalty models.     

Numerical integration of the master equation in some models of stochastic epidemiology

The processes by which disease spreads in a population of individuals are inherently stochastic. The master equation has proven to be a useful tool for modeling such processes. Unfortunately, solving the master equation analytically is possible only in limited cases (e.g., when the model is linear), and thus numerical procedures or approximation methods must be employed. Available approximation methods, such as the system size expansion method of van Kampen, may fail to provide reliable solutions, whereas current numerical approaches can induce appreciable computational cost. In this paper, we propose a new numerical technique for solving the master equation. Our method is based on a more informative stochastic process than the population process commonly used in the literature. By exploiting the structure of the master equation governing this process, we develop a novel technique for calculating the exact solution of the master equation--up to a desired precision--in certain models of stochastic epidemiology. We demonstrate the potential of our method by solving the master equation associated with the stochastic SIR epidemic model. MATLAB software that implements the methods discussed in this paper is freely available as Supporting Information S1.     

The inactivation principle: mathematical solutions minimizing the absolute work and biological implications for the planning of arm movements

An important question in the literature focusing on motor control is to determine which laws drive biological limb movements. This question has prompted numerous investigations analyzing arm movements in both humans and monkeys. Many theories assume that among all possible movements the one actually performed satisfies an optimality criterion. In the framework of optimal control theory, a first approach is to choose a cost function and test whether the proposed model fits with experimental data. A second approach (generally considered as the more difficult) is to infer the cost function from behavioral data. The cost proposed here includes a term called the absolute work of forces, reflecting the mechanical energy expenditure. Contrary to most investigations studying optimality principles of arm movements, this model has the particularity of using a cost function that is not smooth. First, a mathematical theory related to both direct and inverse optimal control approaches is presented. The first theoretical result is the Inactivation Principle, according to which minimizing a term similar to the absolute work implies simultaneous inactivation of agonistic and antagonistic muscles acting on a single joint, near the time of peak velocity. The second theoretical result is that, conversely, the presence of non-smoothness in the cost function is a necessary condition for the existence of such inactivation. Second, during an experimental study, participants were asked to perform fast vertical arm movements with one, two, and three degrees of freedom. Observed trajectories, velocity profiles, and final postures were accurately simulated by the model. In accordance, electromyographic signals showed brief simultaneous inactivation of opposing muscles during movements. Thus, assuming that human movements are optimal with respect to a certain integral cost, the minimization of an absolute-work-like cost is supported by experimental observations. Such types of optimality criteria may be applied to a large range of biological movements.     

An Efficacious Multi-Objective Fuzzy Linear Programming Approach for Optimal Power Flow Considering Distributed Generation

This paper proposes a new formulation for the multi-objective optimal power flow (MOOPF) problem for meshed power networks considering distributed generation. An efficacious multi-objective fuzzy linear programming optimization (MFLP) algorithm is proposed to solve the aforementioned problem with and without considering the distributed generation (DG) effect. A variant combination of objectives is considered for simultaneous optimization, including power loss, voltage stability, and shunt capacitors MVAR reserve. Fuzzy membership functions for these objectives are designed with extreme targets, whereas the inequality constraints are treated as hard constraints. The multi-objective fuzzy optimal power flow (OPF) formulation was converted into a crisp OPF in a successive linear programming (SLP) framework and solved using an efficient interior point method (IPM). To test the efficacy of the proposed approach, simulations are performed on the IEEE 30-busand IEEE 118-bus test systems. The MFLP optimization is solved for several optimization cases. The obtained results are compared with those presented in the literature. A unique solution with a high satisfaction for the assigned targets is gained. Results demonstrate the effectiveness of the proposed MFLP technique in terms of solution optimality and rapid convergence. Moreover, the results indicate that using the optimal DG location with the MFLP algorithm provides the solution with the highest quality.