Sac à dos multidimensionnel en variables 0-1 : encadrement de la somme des variables à l'optimum
Saddle point criteria for second order -approximated vector optimization problems
The purpose of this paper is to apply second order -approximation method introduced to optimization theory by Antczak [2] to obtain a new second order -saddle point criteria for vector optimization problems involving second order invex functions. Therefore, a second order -saddle point and the second order -Lagrange function are defined for the second order -approximated vector optimization problem constructed in this approach. Then, the equivalence between an (weak) efficient solution of the...
Saddle point problems, bilevel problems, and mathematical program with equilibrium constraint on complete metric spaces.
Saddle points criteria via a second order -approximation approach for nonlinear mathematical programming involving second order invex functions
In this paper, by using the second order -approximation method introduced by Antczak [3], new saddle point results are obtained for a nonlinear mathematical programming problem involving second order invex functions with respect to the same function . Moreover, a second order -saddle point and a second order -Lagrange function are defined for the so-called second order -approximated optimization problem constructed in this method. Then, the equivalence between an optimal solution in the original...
Sample path average optimality of Markov control processes with strictly unbounded cost
We study the existence of sample path average cost (SPAC-) optimal policies for Markov control processes on Borel spaces with strictly unbounded costs, i.e., costs that grow without bound on the complement of compact subsets. Assuming only that the cost function is lower semicontinuous and that the transition law is weakly continuous, we show the existence of a relaxed policy with 'minimal' expected average cost and that the optimal average cost is the limit of discounted programs. Moreover, we...
Sample-path analysis of the proportional relation and its constant for discrete-time single-server queues.
Sample-path average cost optimality for semi-Markov control processes on Borel spaces: unbounded costs and mean holding times
We deal with semi-Markov control processes (SMCPs) on Borel spaces with unbounded cost and mean holding time. Under suitable growth conditions on the cost function and the mean holding time, together with stability properties of the embedded Markov chains, we show the equivalence of several average cost criteria as well as the existence of stationary optimal policies with respect to each of these criteria.
Scaling problems in linear-fractional programming.
Scatter Search Based Metaheuristic for Robust Optimization of the Deploying Of “Dwdm” Technology on Optical Networks With Survivability
Scenario generation with distribution functions and correlations
In this paper, we present a method for generating scenarios for two-stage stochastic programs, using multivariate distributions specified by their marginal distributions and the correlation matrix. The margins are described by their cumulative distribution functions and we allow each margin to be of different type. We demonstrate the method on a model from stochastic service network design and show that it improves the stability of the scenario-generation process, compared to both sampling and a...
Scheduling an interval ordered precedence graph with communication delays and a limited number of processors
We consider the scheduling of an interval order precedence graph of unit execution time tasks with communication delays, release dates and deadlines. Tasks must be executed by a set of processors partitioned into K classes; each task requires one processor from a fixed class. The aim of this paper is to study the extension of the Leung–Palem–Pnueli (in short LPP) algorithm to this problem. The main result is to prove that the LPP algorithm can be extended to dedicated processors and monotone communication...
Scheduling electric power generators using particle swarm optimization combined with the lagrangian relaxation method
This paper describes a procedure that uses particle swarm optimization (PSO) combined with the Lagrangian Relaxation (LR) framework to solve a power-generator scheduling problem known as the unit commitment problem (UCP). The UCP consists of determining the schedule and production amount of generating units within a power system subject to operating constraints. The LR framework is applied to relax coupling constraints of the optimization problem. Thus, the UCP is separated into independent optimization...
Scheduling in the presence of processor networks : complexity and approximation
In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks i and j depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes 𝒩𝒫-complete when the length of the schedule ...
Scheduling in the presence of processor networks : complexity and approximation
In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks i and j depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes 𝒩𝒫-complete when the length of the schedule ...
Scheduling jobs in open shops with limited machine availability
In this paper, open shop scheduling problems with limited machine availability are studied. Such a limited availability of machines may appear in many real-life situations, e.g. as preventive maintenance activities. Three types of jobs are distinguished: non-preemptable, resumable and preemptable. An operation of a resumable job if not completed before a non-availability period of a machine may be suspended and continued without additional cost when the machine becomes available. In the paper, results...
Scheduling jobs in open shops with limited machine availability
In this paper, open shop scheduling problems with limited machine availability are studied. Such a limited availability of machines may appear in many real-life situations, e.g. as preventive maintenance activities. Three types of jobs are distinguished: non-preemptable, resumable and preemptable. An operation of a resumable job if not completed before a non-availability period of a machine may be suspended and continued without additional cost when the machine becomes available. In the paper,...
Scheduling multiprocessor tasks on two parallel processors
In this work scheduling multiprocessor tasks on two parallel identical processors is considered. Multiprocessor tasks can be executed by more than one processor at the same moment of time. We analyze scheduling unit execution time and preemptable tasks to minimize schedule length and maximum lateness. Cases with ready times, due-dates and precedence constraints are discussed.
Scheduling multiprocessor tasks on two parallel processors
In this work scheduling multiprocessor tasks on two parallel identical processors is considered. Multiprocessor tasks can be executed by more than one processor at the same moment of time. We analyze scheduling unit execution time and preemptable tasks to minimize schedule length and maximum lateness. Cases with ready times, due-dates and precedence constraints are discussed.
Scheduling partial round Robin tournaments subject to home away pattern sets.
Scheduling problems with a common due window assignment: A survey
In this article a survey of studies on scheduling problems with a common due window assignment and earliness/tardiness penalty functions is presented. A due window is a generalization of the classical due date and describes a time interval in which a job should be finished. If a job is completed before or after the due window, it incurs an earliness or a tardiness penalty, respectively. In this survey we separately analyse the classical models with job-independent and job-dependent earliness/tardiness...