Beyond Smith's rule: An optimal dynamic index, rule for single machine stochastic scheduling with convex holding costs

Most research on single machine scheduling has assumedthe linearity of job holding costs, which is arguablynot appropriate in some applications. This motivates ourstudy of a model for scheduling $n$ classes of stochasticjobs on a single machine, with the objective of minimizingthe total expected holding cost (discounted or undiscounted). We allow general holding cost rates that are separable,nondecreasing and convex on the number of jobs in eachclass. We formulate the problem as a linear program overa certain greedoid polytope, and establish that it issolved optimally by a dynamic (priority) index rule,whichextends the classical Smith's rule (1956) for the linearcase. Unlike Smith's indices, defined for each class, ournew indices are defined for each extended class, consistingof a class and a number of jobs in that class, and yieldan optimal dynamic index rule: work at each time on a jobwhose current extended class has larger index. We furthershow that the indices possess a decomposition property,as they are computed separately for each class, andinterpret them in economic terms as marginal expected cost rate reductions per unit of expected processing time.We establish the results by deploying a methodology recentlyintroduced by us [J. Niño-Mora (1999). "Restless bandits,partial conservation laws, and indexability. "Forthcomingin Advances in Applied Probability Vol. 33 No. 1, 2001],based on the satisfaction by performance measures of partialconservation laws (PCL) (which extend the generalizedconservation laws of Bertsimas and Niño-Mora (1996)):PCL provide a polyhedral framework for establishing theoptimality of index policies with special structure inscheduling problems under admissible objectives, which weapply to the model of concern.

Parallel scheduling of multiclass M/M/m queues: Approximate and heavy-traffic optimization of achievable performance

We address the problem of scheduling a multiclass $M/M/m$ queue with Bernoulli feedback on $m$ parallel servers to minimize time-average linear holding costs. We analyze the performance of a heuristic priority-index rule, which extends Klimov's optimal solution to the single-server case: servers select preemptively customers with larger Klimov indices. We present closed-form suboptimality bounds (approximate optimality) for Klimov's rule, which imply that its suboptimality gap is uniformly bounded above with respect to (i) external arrival rates, as long as they stay within system capacity;and (ii) the number of servers. It follows that its relativesuboptimality gap vanishes in a heavy-traffic limit, as external arrival rates approach system capacity (heavy-traffic optimality). We obtain simpler expressions for the special no-feedback case, where the heuristic reduces to the classical $c \mu$ rule. Our analysis is based on comparing the expected cost of Klimov's ruleto the value of a strong linear programming (LP) relaxation of the system's region of achievable performance of mean queue lengths. In order to obtain this relaxation, we derive and exploit a new set ofwork decomposition laws for the parallel-server system. We further report on the results of a computational study on the quality of the $c \mu$ rule for parallel scheduling.

Restless bandits, linear programming relaxations and a primal-dual index heuristic

We develop a mathematical programming approach for the classicalPSPACE - hard restless bandit problem in stochastic optimization.We introduce a hierarchy of n (where n is the number of bandits)increasingly stronger linear programming relaxations, the lastof which is exact and corresponds to the (exponential size)formulation of the problem as a Markov decision chain, while theother relaxations provide bounds and are efficiently computed. Wealso propose a priority-index heuristic scheduling policy fromthe solution to the first-order relaxation, where the indices aredefined in terms of optimal dual variables. In this way wepropose a policy and a suboptimality guarantee. We report resultsof computational experiments that suggest that the proposedheuristic policy is nearly optimal. Moreover, the second-orderrelaxation is found to provide strong bounds on the optimalvalue.

Priority areas for the conservation of Atlantic forest large mammals

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Características oclusais de pacientes com Classe II, divisão 1, tratados sem e com extrações de dois pré-molares superiores

OBJETIVOS: o objetivo deste estudo foi identificar características oclusais iniciais de pacientes Classe II, divisão 1, tratados sem e com extrações de dois pré-molares superiores. MÉTODOS: foram selecionados 62 pacientes que apresentavam má oclusão de Classe II, divisão 1, os quais foram divididos em dois grupos, de acordo com a forma de tratamento proposta, sendo o grupo 1 constituído de 42 pacientes (23 do sexo feminino e 19 do sexo masculino), com idade média de 12,7 anos, tratados sem extrações e com aparelho fixo combinado com extrabucal; e o grupo 2, composto de 20 pacientes (6 do sexo feminino e 14 do sexo masculino), com idade média de 13,5 anos, tratados também com aparelho fixo combinado com uso de extrabucal, mas que tiveram indicação de extrações de dois pré-molares superiores em seus planos de tratamento. Para observar as características oclusais iniciais e finais, assim como suas alterações com o tratamento, foi utilizado o Índice de Prioridade de Tratamento (IPT). Os valores dos índices foram submetidos à análise estatística pelo teste t independente, para comparar as variáveis entre os grupos. RESULTADOS E CONCLUSÕES: os resultados demonstraram que o grau de má oclusão inicial foi diferente nos dois grupos quando avaliados pelo IPT, sendo maior no grupo tratado com extrações de dois pré-molares superiores

Effects of the pendulum appliance, cervical headgear, and 2 premolar extractions followed by fixed appliances in patients with Class II malocclusion

Introduction: In this retrospective study, we compared the cephalometric effects, the dental-arch changes, and the efficiency of Class II treatment with the pendulum appliance, cervical headgear, or extraction of 2 maxillary premolars, all associated with fixed appliance therapy. Methods: The sample of 82 patients with Class II malocclusion was divided into 3 groups: group 1 patients (n = 22; treatment time, 3.8 years) were treated with the pendulum appliance and fixed orthodontic appliances. Group 2 patients (n = 30; treatment time, 3.2 years) were treated with cervical headgear followed by fixed appliances; group 3 patients (n = 30; treatment time, 2.1 years) were treated with 2 maxillary premolar extractions and fixed appliances. The average starting ages of the groups ranged from 13.2 to 13.8 years. Data were obtained from serial cephalometric measurements and dental casts. The dental casts were analyzed with the treatment priority index. The treatment efficiency index was also used. Results: The 3 treatment protocols produced similar cephalometric effects, especially skeletally. Comparisons among the 2 distalizing appliances (pendulum and cervical headgear) and extraction of 2 maxillary premolars for Class II treatment showed changes primarily in the maxillary dentoalveolar component and dental relationships. The facial profile was similar after treatment, except for slightly more retrusion of the upper lip in the extraction patients. The treatment priority index demonstrated that occlusal outcomes also were similar among the groups. The treatment efficiency index had higher values for the extraction group. Conclusions: The effects of treatment with the pendulum appliance or cervical headgear and extraction of 2 maxillary premolars associated with fixed appliances were similar from both occlusal and cephalometric standpoints. Class II treatment with extraction of maxillary teeth was more efficient because of the shorter treatment time. Differences in maxillary incisor retraction should be noted, but these differences might have been due to greater maxillary dentoalveolar protrusion in the extraction group before treatment. (Am J Orthod Dentofacial Orthop 2009;136:833-42)

Relationship between malocclusion severity and treatment success rate in Class II nonextraction therapy

Introduction: The purpose of this study was to evaluate the treatment success rate of Class II malocclusion without extractions, according to initial severity. Methods: Class II subjects (n = 276) were divided into 2 groups according to the severity of the malocclusion. Group 1 comprised 144 patients with bilateral half Class II malocclusion at the initial mean age of 12.27 years. Group 2 comprised 132 patients who initially had bilateral complete Class II malocclusion at the initial mean age of 12.32 years. The patients` initial and final study models were evaluated with Grainger`s treatment priority index. Chi-square tests were used to test for differences between the 2 groups for categorical variables. Variables regarding occlusal results were compared with independent t tests. Results: Group 1 had a significantly better final occlusal result, a shorter treatment time, and a higher treatment efficiency index. Conclusions: Based on these results, it was concluded that bilateral half Class II malocclusion has a better treatment success rate than bilateral complete Class II malocclusion when treatment is conducted without extractions. (Am J Orthod Dentofacial Orthop 2009; 135: 274.e1-274.e8)

Comparison of the effects produced by headgear and pendulum appliances followed by fixed orthodontic treatment

This study compared the effects produced by two different molar distalizers, namely cervical headgear (CHG) and the intraoral pendulum appliance, associated with fixed orthodontic appliances. The headgear group comprised 30 patients (19 females, 11 males), with an initial age of 13.07 years [standard deviation (SD) = 1.3], treated with CHG and fixed orthodontic appliances for a mean period of 3.28 years, and the pendulum group 22 patients (15 females, 7 males), with initial age of 13.75 years (SD = 1.86), treated with the pendulum appliance followed by fixed orthodontic appliances for a mean period of 4.12 years. Lateral cephalograms were taken at the start (T1) and on completion (T2) of orthodontic treatment. The pendulum and CHG groups were similar as to initial age, severity of the Class II malocclusion, gender distribution, initial cephalometric characteristics, and initial and final treatment priority index (TPI). Only treatment time was not similar between the groups, with a need for annualization for data for the pendulum group. The data were compared with independent t-tests. There was significantly greater restriction of maxillary forward growth and improvement of the skeletal maxillomandibular relationship in the CHG group (P < 0.05). The maxillary molars were more mesially tipped and extruded and the mandibular molars more uprighted in the CHG group compared with the pendulum group (P < 0.05). There was more labial tipping of the mandibular incisors and greater overbite reduction in the pendulum group. The pendulum appliance produced only dentoalveolar effects, different from the CHG appliance, which restricted maxillary forward displacement, thus improving the skeletal maxillomandibular relationship.

Influence of cephalometric characteristics on the occlusal success rate of Class II malocclusions treated with 2-and 4-premolar extraction protocols

Introduction: The objectives of this investigation were to compare the initial cephalometric characteristics of complete Class II Division 1 malocclusions treated with 2 or 4 premolar extractions and to verify their influence on the occlusal success rate of these treatment protocols. Methods: A sample of 98 records from patients with complete Class II Division 1 malocclusion was divided into 2 groups with the following characteristics: group 1 consisted of 55 patients treated with 2 maxillary first premolar extractions at an initial mean age of 13.07 years; group 2 included 43 patients treated with 4 premolar extractions, with an initial mean age of 12.92 years. Initial and final occlusal statuses were evaluated on dental casts with Grainger`s treatment priority index (TPI), and the initial cephalometric characteristics were obtained from the pretreatment cephalograms. The initial cephalometric characteristics and the initial and final occlusal statuses of the groups were compared with the t test. A multiple regression analysis was used to evaluate the influence of all variables in the final TPI. Results: The 2-premolar extraction protocol provided a statistically smaller TPI and consequently a better occlusal success rate than the 4-premolar extraction protocol. The 4-premolar extraction group had statistically smaller apical base lengths, more vertical facial growth patterns, and greater hard- and soft-tissue convexities at pretreatment than the 2-premolar extraction group. However, the multiple regression analysis showed that only the extraction protocol was significantly associated with the final occlusal status. Conclusions: The initial cephalometric characteristics of the groups did not influence the occlusal success rate of these 2 treatment protocols.

On Certain Greedoid Polyhedra, Partially Indexable Scheduling Problems, and Extended Restless Bandit Allocation Indices

We present a polyhedral framework for establishing general structural properties on optimal solutions of stochastic scheduling problems, where multiple job classes vie for service resources: the existence of an optimal priority policy in a given family, characterized by a greedoid (whose feasible class subsets may receive higher priority), where optimal priorities are determined by class-ranking indices, under restricted linear performance objectives (partial indexability). This framework extends that of Bertsimas and Niño-Mora (1996), which explained the optimality of priority-index policies under all linear objectives (general indexability). We show that, if performance measures satisfy partial conservation laws (with respect to the greedoid), which extend previous generalized conservation laws, then the problem admits a strong LP relaxation over a so-called extended greedoid polytope, which has strong structural and algorithmic properties. We present an adaptive-greedy algorithm (which extends Klimov's) taking as input the linear objective coefficients, which (1) determines whether the optimal LP solution is achievable by a policy in the given family; and (2) if so, computes a set of class-ranking indices that characterize optimal priority policies in the family. In the special case of project scheduling, we show that, under additional conditions, the optimal indices can be computed separately for each project (index decomposition). We further apply the framework to the important restless bandit model (two-action Markov decision chains), obtaining new index policies, that extend Whittle's (1988), and simple sufficient conditions for their validity. These results highlight the power of polyhedral methods (the so-called achievable region approach) in dynamic and stochastic optimization.

On certain greedoid polyhedra, partially indexable scheduling problems and extended restless bandit allocation indices

We present a polyhedral framework for establishing general structural properties on optimal solutions of stochastic scheduling problems, where multiple job classes vie for service resources: the existence of an optimal priority policy in a given family, characterized by a greedoid(whose feasible class subsets may receive higher priority), where optimal priorities are determined by class-ranking indices, under restricted linear performance objectives (partial indexability). This framework extends that of Bertsimas and Niño-Mora (1996), which explained the optimality of priority-index policies under all linear objectives (general indexability). We show that, if performance measures satisfy partial conservation laws (with respect to the greedoid), which extend previous generalized conservation laws, then theproblem admits a strong LP relaxation over a so-called extended greedoid polytope, which has strong structural and algorithmic properties. We present an adaptive-greedy algorithm (which extends Klimov's) taking as input the linear objective coefficients, which (1) determines whether the optimal LP solution is achievable by a policy in the given family; and (2) if so, computes a set of class-ranking indices that characterize optimal priority policies in the family. In the special case of project scheduling, we show that, under additional conditions, the optimal indices can be computed separately for each project (index decomposition). We further apply the framework to the important restless bandit model (two-action Markov decision chains), obtaining new index policies, that extend Whittle's (1988), and simple sufficient conditions for their validity. These results highlight the power of polyhedral methods (the so-called achievable region approach) in dynamic and stochastic optimization.

Restless bandits, partial conservation laws and indexability

We show that if performance measures in a stochastic scheduling problem satisfy a set of so-called partial conservation laws (PCL), which extend previously studied generalized conservation laws (GCL), then the problem is solved optimally by a priority-index policy for an appropriate range of linear performance objectives, where the optimal indices are computed by a one-pass adaptive-greedy algorithm, based on Klimov's. We further apply this framework to investigate the indexability property of restless bandits introduced by Whittle, obtaining the following results: (1) we identify a class of restless bandits (PCL-indexable) which are indexable; membership in this class is tested through a single run of the adaptive-greedy algorithm, which also computes the Whittle indices when the test is positive; this provides a tractable sufficient condition for indexability; (2) we further indentify the class of GCL-indexable bandits, which includes classical bandits, having the property that they are indexable under any linear reward objective. The analysis is based on the so-called achievable region method, as the results follow fromnew linear programming formulations for the problems investigated.

Optimization of multiclass queueing networks with changeover times via the achievable region method: Part II, the multi-station case

We address the problem of scheduling a multi-station multiclassqueueing network (MQNET) with server changeover times to minimizesteady-state mean job holding costs. We present new lower boundson the best achievable cost that emerge as the values ofmathematical programming problems (linear, semidefinite, andconvex) over relaxed formulations of the system's achievableperformance region. The constraints on achievable performancedefining these formulations are obtained by formulatingsystem's equilibrium relations. Our contributions include: (1) aflow conservation interpretation and closed formulae for theconstraints previously derived by the potential function method;(2) new work decomposition laws for MQNETs; (3) new constraints(linear, convex, and semidefinite) on the performance region offirst and second moments of queue lengths for MQNETs; (4) a fastbound for a MQNET with N customer classes computed in N steps; (5)two heuristic scheduling policies: a priority-index policy, anda policy extracted from the solution of a linear programmingrelaxation.

A Survey of mid and large bodied mammals in Núcleo Caraguatatuba, Serra do Mar State Park, Brazil

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Ferramentas da qualidade na colheita mecanizada de cana-de-açúcar

Pós-graduação em Agronomia (Produção Vegetal) - FCAV