The Experts below are selected from a list of 15576 Experts worldwide ranked by ideXlab platform
Avrim Blum - One of the best experts on this subject based on the ideXlab platform.
-
empirical support for winnow and weighted majorityalgorithms results on a calendar Scheduling Domain
Machine Learning, 1997Co-Authors: Avrim BlumAbstract:This paper describes experimental results on using Winnow and Weighted-Majority based algorithms on a real-world calendar Scheduling Domain. These two algorithms have been highly studied in the theoretical machine learning literature. We show here that these algorithms can be quite competitive practically, outperforming the decision-tree approach currently in use in the Calendar Apprentice system in terms of both accuracy and speed. One of the contributions of this paper is a new variant on the Winnow algorithm (used in the experiments) that is especially suited to conditions with string-valued classifications, and we give a theoretical analysis of its performance. In addition we show how Winnow can be applied to achieve a good accuracy/coverage tradeoff and explore issues that arise such as concept drift. We also provide an analysis of a policy for discarding predictors in Weighted-Majority that allows it to speed up as it learns.
-
empirical support for winnow and weighted majority based algorithms results on a calendar Scheduling Domain
International Conference on Machine Learning, 1995Co-Authors: Avrim BlumAbstract:This paper describes experimental results on using Winnow and Weighted-Majority based algorithms on a real-world calendar Scheduling Domain. These two algorithms have been highly studied in the theoretical machine learning literature. We show here that these algorithms can be quite competitive practically, outperforming the decision-tree approach currently in use in the Calendar Apprentice system in terms of both accuracy and speed. One of the contributions of this paper is a new variant on the Winnow algorithm (used in the experiments) that is especially suited to conditions with string-valued classifications, and we give a theoretical analysis of its performance. In addition we show how Winnow can be applied to achieve a good accuracy/coverage tradeoff and explore issues that arise such as concept drift. We also provide an analysis of a policy for discarding predictors in Weighted-Majority that allows it to speed up as it learns.
Mark S Fox - One of the best experts on this subject based on the ideXlab platform.
-
variable and value ordering heuristics for the job shop Scheduling constraint satisfaction problem
Artificial Intelligence, 1996Co-Authors: Norman Sadeh, Mark S FoxAbstract:Abstract Practical constraint satisfaction problems (CSPs) such as design of integrated circuits or Scheduling generally entail large search spaces with hundreds or even thousands of variables, each with hundreds or thousands of possible values. Often, only a very tiny fraction of all these possible assignments participates in a satisfactory solution. This article discusses techniques that aim at reducing the effective size of the search space to be explored in order to find a satisfactory solution by judiciously selecting the order in which variables are instantiated and the sequence in which possible values are tried for each variable. In the CSP literature, these techniques are commonly referred to as variable and value ordering heuristics. Our investigation is conducted in the job shop Scheduling Domain. We show that, in contrast with problems studied earlier in the CSP literature, generic variable and value heuristics do not perform well in this Domain. This is attributed to the difficulty of these heuristics to properly account for the tightness of constraints and/or the connectivity of the constraint graphs induced by job shop Scheduling CSPs. A new probabilistic framework is introduced that better captures these key aspects of the job shop Scheduling search space. Empirical results show that variable and value ordering heuristics derived within this probabilistic framework often yield significant improvements in search efficiency and significant reductions in the search time required to obtain a satisfactory solution. The research reported in this article was the first one, along with the work of Keng and Yun (1989), to use the CSP problem solving paradigm to solve job shop Scheduling problems. The suite of benchmark problems it introduced has been used since then by a number of other researchers to evaluate alternative techniques for the job shop Scheduling CSP. The article briefly reviews some of these more recent efforts and shows that our variable and value ordering heuristics remain quite competitive
Norman Sadeh - One of the best experts on this subject based on the ideXlab platform.
-
variable and value ordering heuristics for the job shop Scheduling constraint satisfaction problem
Artificial Intelligence, 1996Co-Authors: Norman Sadeh, Mark S FoxAbstract:Abstract Practical constraint satisfaction problems (CSPs) such as design of integrated circuits or Scheduling generally entail large search spaces with hundreds or even thousands of variables, each with hundreds or thousands of possible values. Often, only a very tiny fraction of all these possible assignments participates in a satisfactory solution. This article discusses techniques that aim at reducing the effective size of the search space to be explored in order to find a satisfactory solution by judiciously selecting the order in which variables are instantiated and the sequence in which possible values are tried for each variable. In the CSP literature, these techniques are commonly referred to as variable and value ordering heuristics. Our investigation is conducted in the job shop Scheduling Domain. We show that, in contrast with problems studied earlier in the CSP literature, generic variable and value heuristics do not perform well in this Domain. This is attributed to the difficulty of these heuristics to properly account for the tightness of constraints and/or the connectivity of the constraint graphs induced by job shop Scheduling CSPs. A new probabilistic framework is introduced that better captures these key aspects of the job shop Scheduling search space. Empirical results show that variable and value ordering heuristics derived within this probabilistic framework often yield significant improvements in search efficiency and significant reductions in the search time required to obtain a satisfactory solution. The research reported in this article was the first one, along with the work of Keng and Yun (1989), to use the CSP problem solving paradigm to solve job shop Scheduling problems. The suite of benchmark problems it introduced has been used since then by a number of other researchers to evaluate alternative techniques for the job shop Scheduling CSP. The article briefly reviews some of these more recent efforts and shows that our variable and value ordering heuristics remain quite competitive
Mark D Johnston - One of the best experts on this subject based on the ideXlab platform.
-
request driven schedule automation for the deep space network
SpaceOps 2010 Conference, 2010Co-Authors: Mark D Johnston, Daniel Tran, Belinda Arroyo, Jared Call, Marisol MercadoAbstract:The DSN Scheduling Engine (DSE) has been developed to increase the level of automated Scheduling support available to users of NASA s Deep Space Network (DSN). We have adopted a request-driven approach to DSN Scheduling, in contrast to the activity-oriented approach used up to now. Scheduling requests allow users to declaratively specify patterns and conditions on their DSN service allocations, including timing, resource requirements, gaps, overlaps, time linkages among services, repetition, priorities, and a wide range of additional factors and preferences. The DSE incorporates a model of the key constraints and preferences of the DSN Scheduling Domain, along with algorithms to expand Scheduling requests into valid resource allocations, to resolve schedule conflicts, and to repair unsatisfied requests. We use time-bounded systematic search with constraint relaxation to return nearby solutions if exact ones cannot be found, where the relaxation options and order are under user control. To explore the usability aspects of our approach we have developed a graphical user interface incorporating some crucial features to make it easier to work with complex Scheduling requests. Among these are: progressive revelation of relevant detail, immediate propagation and visual feedback from a user s decisions, and a meeting calendar metaphor for repeated patterns of requests. Even as a prototype, the DSE has been deployed and adopted as the initial step in building the operational DSN schedule, thus representing an important initial validation of our overall approach. The DSE is a core element of the DSN Service Scheduling Software (S(sup 3)), a web-based collaborative Scheduling system now under development for deployment to all DSN users.
-
request driven Scheduling for nasa s deep space network
2009Co-Authors: Mark D Johnston, Daniel Tran, Belinda Arroyo, Chris PageAbstract:This paper describes recent work undertaken to increase the level of automated Scheduling support available to users of NASA’s Deep Space Network (DSN). We have adopted a request-driven approach to DSN Scheduling, in contrast to the activity-oriented approach used up to now. We describe some of the key constraints and preferences of the DSN Scheduling Domain and how we have modeled these as Scheduling requests. Algorithms to expand requests into valid resource allocations, and to resolve schedule conflicts and unsatisfied requests, have been developed and incorporated into a distributed system of servers called the DSN Scheduling Engine (DSE). To explore the usability aspects of our approach we have developed a pathfinder graphical user interface that utilizes the DSE. This GUI incorporates several key features to make it easier to work with complex Scheduling requests, including progressive revelation of detail, immediate propagation and feedback of implications, and a “meeting calendar” metaphor for repeated patterns of requests. This pathfinder system has been deployed and adopted by one of the JPL DSN Scheduling teams, representing an initial validation of our overall approach. The DSE is planned to be a central element of the Service Scheduling Software (S 3 ) web-based Scheduling system now under development for deployment to all DSN users.
Radoslaw Rudek - One of the best experts on this subject based on the ideXlab platform.
-
experience based approach to Scheduling problems with the learning effect
Systems Man and Cybernetics, 2009Co-Authors: Adam Janiak, Radoslaw RudekAbstract:The existence of the learning effect in many manufacturing systems is undoubted; thus, it is worthwhile that it be taken into consideration during production planning to increase production efficiency. Generally, it can be done by formulating the specified problem in the Scheduling context and optimizing an order of jobs to minimize the given time criteria. To carry out a reliable study of the learning effect in Scheduling fields, a comprehensive survey of the related results is presented first. It reveals that most of the learning models in Scheduling are based on the learning curve introduced by Wright. However, further study about learning itself pointed out that the curve may be an ldquoSrdquo-shaped function, which has not been considered in the Scheduling Domain. To fill this gap, we analyze a Scheduling problem with a new experience-based learning model, where job processing times are described by ldquoSrdquo-shaped functions that are dependent on the experience of the processor. Moreover, problems with other experience-based learning models are also taken into consideration. We prove that the makespan minimization problem on a single processor is NP-hard or strongly NP-hard with the most of the considered learning models. A number of polynomially solvable cases are also provided.
