293 research outputs found
‘Strong’–‘weak’ precedence in scheduling: Extensions to series–parallel orders
No full textAbstractWe examine computational complexity implications for scheduling problems with job precedence relations with respect to strong precedence versus weak precedence. We propose a consistent definition of strong precedence for chains, trees, and series–parallel orders. Using modular decomposition for partially ordered sets (posets), we restate and extend past complexity results for chains and trees as summarized in Dror (1997) [5]. Moreover, for series–parallel posets we establish new computational complexity results for strong precedence constraints for single- and multi-machine problems
Recommended from our members
Decision support for multi-objective linear programming using an interactive graphic presentation.
No full textMany decisions in real world applications are based on conflicting criteria or objectives. In order to improve one objective, it is necessary to sacrifice another. Linear programming has long been used to optimize a single objective. When a linear programming problem involves multiple objectives (MOLP), it is usually not possible to locate a single solution that simultaneously optimizes all objectives. Hence, a methodology is needed to help the decision maker (DM) explore the space of feasible solutions in order to locate an acceptable compromise solution. An interactive approach that supports the DM in the exploration process is presented. The methodology is implemented on a microcomputer running a graphical user interface. The computations are based on an expansion of the Dror-Gass (1987) methodology in which candidate solutions are located using weak order preferences for variables and objectives. It differs from previous methodologies in that it does not require burdensome trade-off ratios or strength of preference comparisons. During exploration, the DM is presented a multi-faceted graphical representation of solutions for consideration. Previous studies of the effectiveness of graphics to support the decision making process have used static presentations of the data. The graphic presentation as implemented is dynamic. It makes use of animation, interactive zoom (or inspect), and interactive highlighting of the results to improve its effectiveness. In the design of the interface, special attention was paid to the requirements for supporting interaction with large LP problems. The software implementation and methodology were tested by subjects drawn from faculty and students at the University of Arizona. It was also reviewed in industry. The results are presented.This item was digitized from a paper original and/or a microfilm copy. If you need higher-resolution images for any content in this item, please contact us at [email protected] file replaced with corrected file May 2023
Recommended from our members
Agent-based heuristics for large, multiple-mode, resource-constrained project scheduling problems
No full textIn this dissertation we address large, multiple-mode, resource-constrained project scheduling problems with the objective of minimizing makespan. After noting that projects often fail and new research is needed, we provide the formal definition of the resource-constrained project scheduling problem and review the existing literature. We then introduce a new model based on digital electronics. We conceptualize our model using agent technology and discuss it as extension of existing models with more representational power. We also describe how our model supports distributed planning. After implementing our model, we conduct two computational studies. In the first, we develop two agent types: basic and enhanced where the enhanced agent is more sophisticated in selecting an activity execution mode. We apply these agents to the scheduling of 500 instances of a small project originally published by Maroto and Tormos (1994). We evaluate the performance of the agents in conjunction with their use of eight heuristic prioritization rules: shortest and longest processing time, fewest and most immediate successors, smallest and greatest resource demand, earliest start time, and earliest due date. Our results show that enhanced agents consistently outperform basic agents while the results regarding priority rules were mixed. In the second computational study, we further develop our enhanced agents by providing still more sophisticated mode selection. We also evaluate static versus dynamic prioritization and two more priority rules: shortest and longest duration critical path. For this study we generated 2500, 5000, 7500, and 10000 activity projects. For each of these, we generated networks with complexities of 1.5, 1.8, and 2.1. For these twelve networks, we generated 20 problem instances for every possible combination of resource factor = 0.25, 0.50, 0.75, 1.0 and resource strength = 0.2, 0.5, 0.8. We graphically evaluated scheduling performance, computation times, and failure rates and conducted an extensive statistical analysis. We found that enhanced agents using shortest processing time priority consistently produced the shortest schedules. However, these agents fail more often than basic agents. We found that dynamic prioritization requires more computation time, but provides little improvement in scheduling performance. We conclude this work with suggestions for future research.This item was digitized from a paper original and/or a microfilm copy. If you need higher-resolution images for any content in this item, please contact us at [email protected] file replaced with corrected file September 2023
Recommended from our members
Domain-independent semantic concept extraction using corpus linguistics, statistics and artificial intelligence techniques
No full textFor this dissertation two software applications were developed and three experiments were conducted to evaluate the viability of a unique approach to medical information extraction. The first system, the AZ Noun Phraser, was designed as a concept extraction tool. The second application, ANNEE, is a neural net-based entity extraction (EE) system. These two systems were combined to perform concept extraction and semantic classification specifically for use in medical document retrieval systems. The goal of this research was to create a system that automatically (without human interaction) enabled semantic type assignment, such as gene name and disease, to concepts extracted from unstructured medical text documents. Improving conceptual analysis of search phrases has been shown to improve the precision of information retrieval systems. Enabling this capability in the field of medicine can aid medical researchers, doctors and librarians in locating information, potentially improving healthcare decision-making. Due to the flexibility and non-domain specificity of the implementation, these applications have also been successfully deployed in other text retrieval experimentation for law enforcement (Atabakhsh et al., 2001; Hauck, Atabakhsh, Ongvasith, Gupta, & Chen, 2002), medicine (Tolle & Chen, 2000), query expansion (Leroy, Tolle, & Chen, 2000), web document categorization (Chen, Fan, Chau, & Zeng, 2001), Internet spiders (Chau, Zeng, & Chen, 2001), collaborative agents (Chau, Zeng, Chen, Huang, & Hendriawan, 2002), competitive intelligence (Chen, Chau, & Zeng, 2002), and Internet chat-room data visualization (Zhu & Chen, 2001)
Recommended from our members
Capacitated rural postman problem with time windows and split delivery
No full textThe importance of effective and efficient distribution is evident from its associated costs. Transportation and shipping alone comprise roughly 15 percent of a product's sales in the U.S. Physical distribution is very energy and labor intensive, which have both become relatively more expensive in the last 10-15 years. Not surprisingly, there is a growing demand for automated planning systems that produce economical routes. Other than the cost savings, introduction of these systems enables companies to maintain a higher level of service for their customers, it makes them less dependent on human planners, it supplies better management information facilities and it makes distribution planning work faster and simpler.This item was digitized from a paper original and/or a microfilm copy. If you need higher-resolution images for any content in this item, please contact us at [email protected] file replaced with corrected file October 2023
Sequential Relational Decomposition
No full textThe concept of decomposition in computer science and engineering is
considered a fundamental component of computational thinking and is prevalent
in design of algorithms, software construction, hardware design, and more. We
propose a simple and natural formalization of sequential decomposition, in
which a task is decomposed into two sequential sub-tasks, with the first
sub-task to be executed before the second sub-task is executed. These tasks are
specified by means of input/output relations. We define and study decomposition
problems, which is to decide whether a given specification can be sequentially
decomposed. Our main result is that decomposition itself is a difficult
computational problem. More specifically, we study decomposition problems in
three settings: where the input task is specified explicitly, by means of
Boolean circuits, and by means of automatic relations. We show that in the
first setting decomposition is NP-complete, in the second setting it is
NEXPTIME-complete, and in the third setting there is evidence to suggest that
it is undecidable. Our results indicate that the intuitive idea of
decomposition as a system-design approach requires further investigation. In
particular, we show that adding a human to the loop by asking for a
decomposition hint lowers the complexity of decomposition problems
considerably
The power of foregone payoffs: a mousetracking study
No full textBehavior in two-player laboratory games has been observed to depend upon choices that the other player "could have made," in violation of the principle of subgame perfection. Models of other-regarding preferences that only transform payoffs at end-nodes (e.g. inequality aversion) cannot explain this behavior, and various explanations (e.g. models of intention-based reciprocity) have been proposed. We explore the mechanisms by which foregone payoffs influence decision-making in a variety of two-player, two-stage games using mousetracking, a technology that allows us to observe which payoffs subjects attend to, and for how long, when making strategic decisions
Aggregate Matchings
No full textThis paper characterizes the testable implications of stability for aggregate matchings. We consider data on matchings where individuals are aggregated, based on their observable characteristics, into types, and we know how many agents of each type match. We derive stability conditions for an aggregate matching, and, based on these, provide a simple necessary and sufficient condition for an observed aggregate matching to be rationalizable (i.e. such that preferences can be found so that the observed aggregate matching is stable). Subsequently, we derive moment inequalities based on the stability conditions, and provide an empirical illustration using the cross-sectional marriage distributions across the US states
- …
