We combine mixed integer linear programming (MILP) and constraint programming (CP) to minimize tardiness in planning and scheduling. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are...
详细信息
ISBN:
(纸本)3540292381
We combine mixed integer linear programming (MILP) and constraint programming (CP) to minimize tardiness in planning and scheduling. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-based Benders decomposition. We consider two objectives: minimizing the number of late tasks, and minimizing total tardiness. Our main theoretical contribution is a relaxation of the cumulative scheduling subproblem, which is critical to performance. We obtain substantial computational speedups relative to the state of the art in both MILP and CR We also obtain much better solutions for problems that cannot be solved to optimality.
Poorly structured code is hard to maintain and read Program refactoring can improve code structure and thus make it easier to preserve and to discern the underlying design. However, refactoring is a difficult and time...
详细信息
ISBN:
(纸本)0769524656
Poorly structured code is hard to maintain and read Program refactoring can improve code structure and thus make it easier to preserve and to discern the underlying design. However, refactoring is a difficult and time-consuming process making it unattractive for many developers. An automated tool that could identify poorly structured code and make suggest ions would make the refactoring process easier. Although in general refactorings may be quite difficult to locate automatically, we show that many can be detected using low-cost, syntactic techniques. We have built a tool to locate refactorings in C# programs. Our experiments indicate that the tool has an excellent success rate in identifying refactorings.
We explore the nature of the interaction between organisational culture and XP practice via three empirically-based case studies. The case studies cover a spectrum of organisational cultures. Our findings suggest that...
详细信息
ISBN:
(纸本)0769524877
We explore the nature of the interaction between organisational culture and XP practice via three empirically-based case studies. The case studies cover a spectrum of organisational cultures. Our findings suggest that XP can thrive in a range of organisational cultures and that the interaction between organisational culture and XP can be complex & subtle, with consequences for practice.
One of the most important goals of an introductory programming course is that the students learn a systematic approach to the development of computer programs. Revealing the programming process is an important part of...
详细信息
ISBN:
(纸本)1581139977
One of the most important goals of an introductory programming course is that the students learn a systematic approach to the development of computer programs. Revealing the programming process is an important part of this;however, textbooks do not address the issue - probably because the textbook medium is static and therefore ill-suited to expose the process of programming. We have found that process recordings in the form of captured narrated programming sessions are a simple, cheap, and efficient way of providing the revelation. We identify seven different elements of the programming process for which process recordings are a valuable communication media in order to enhance the learning process. Student feedback indicates both high learning outcome and superior learning potential compared to traditional classroom teaching. Copyright 2005 ACM.
Invariant based programming is an approach to program construction where we provide the program pre- and postconditions as well as loop invariants before we construct the code itself. This approach allows us to constr...
详细信息
ISBN:
(纸本)0769524656
Invariant based programming is an approach to program construction where we provide the program pre- and postconditions as well as loop invariants before we construct the code itself. This approach allows us to construct a program and its correctness proof hand in hand. We describe here an extension to an existing mathematics editor that supports this style of program construction. The main help that the tool provides is automatic simplification of verification conditions that are generated in the programming process. The tool shows the user a check list of those conditions that it was not able to prove automatically. The user can use this check list to complete the proof (either manually or using an interactive theorem prover) or to find errors in the program.
Answer Set programming (ASP) is a declarative paradigm for solving search problems. State-of-the-art systems for ASP include SMODELS, DLV, CMODELS, and ASSAT. In this paper, our goal is to study the computational prop...
详细信息
ISBN:
(纸本)354029208X
Answer Set programming (ASP) is a declarative paradigm for solving search problems. State-of-the-art systems for ASP include SMODELS, DLV, CMODELS, and ASSAT. In this paper, our goal is to study the computational properties of such systems both from a theoretical and an experimental point of view. From the theoretical point of view, we start our analysis with CMODELS and SMODELS. We show that though these two systems are apparently different, they are equivalent on a significant class of programs, called tight. By equivalent, we mean that they explore search trees with the same branching nodes, (assuming, of course, a same branching heuristic). Given our result and that the CMODELS search engine is based on the Davis Logemann Loveland procedure (DLL) for propositional satisfiability (SAT), we are able to establish that many of the properties holding for DLL also hold for CMODELS and thus for SMODELS. On the other hand, we also show that there exist classes of non-tight programs which are exponentially hard for CMODELS, but "easy" for SMODELS. We also discuss how our results extend to other systems. From the experimental point of view, we analyze which combinations of reasoning strategies work best on which problems. In particular, we extended CMODELS in order to obtain a unique platform with a variety of reasoning strategies, and conducted an extensive experimental analysis on "small" randomly generated and on "large" non randomly generated programs. Considering these programs, our results show that the reasoning strategies that work best on the small problems are completely different from the ones that are best on the large ones. These results point out, e.g., that we can hardly expect to develop one solver with the best performances on all the categories of problems. As a consequence, (i) developers should focus on specific classes of benchmarks, and (ii) benchmarking should take into account whether solvers have been designed for specific classes of programs.
The prevalence of weblogs (blogs) has enabled people to share the personal experiences of tourists at specific locations and times. Such information was traditionally unavailable, except indirectly through local newsp...
详细信息
ISBN:
(纸本)3540300171
The prevalence of weblogs (blogs) has enabled people to share the personal experiences of tourists at specific locations and times. Such information was traditionally unavailable, except indirectly through local newspapers and periodicals. This paper describes a method of spatially and temporally obtaining specific experiences by extracting association rules from the content of blog articles. For example, we can read about visitors' activities and evaluations of sightseeing spots. By geographically mapping their experiences, the proposed system enables observation of tourist activities and impressions of specific locations, which can often be more diverse than local guidebooks and more trustworthy than advertisements.
Message-passing programs are difficult to test because of their non-deterministic behavior. One approach, called non-deterministic testing, involves executing a message-passing program with the same input many times i...
详细信息
ISBN:
(纸本)0769523773
Message-passing programs are difficult to test because of their non-deterministic behavior. One approach, called non-deterministic testing, involves executing a message-passing program with the same input many times in hope that faults will be exposed by one of these executions. Non-deterministic testing has been widely used in practice, but unfortunately, in an adhoc manner. In this paper, we present a novel framework for non-deterministic testing of message-passing programs. The framework uses a coverage criterion to guide the testing process. During each test run, the sequence of send and receive events that are executed is recorded in an execution trace. After each test run, the trace is analyzed to identify race conditions, which are used to derive coverage elements that have not been covered yet. Then, random delays are inserted at a chosen set of program locations in order to increase the chance of covering the uncovered elements in the next test run. This framework provides a heuristic condition that can be used to decide when to stop testing. The condition is easy to compute and its satisfaction signals that the coverage criterion has likely been satisfied. This framework can be automated at the source code level and allows one to obtain a measure of test coverage at the end of the testing process. We describe a prototype tool and report some empirical results that demonstrate the effectiveness of our framework.
The information generated by pacemakers and ICD's to support the cardiologist and technician for installing the optimal settings for the patient is increasing rapidly. In this paper a proposal is described for ele...
详细信息
ISBN:
(纸本)0780393376
The information generated by pacemakers and ICD's to support the cardiologist and technician for installing the optimal settings for the patient is increasing rapidly. In this paper a proposal is described for electronic data exchange between the pacemaker/ICD programmers and electronic information systems.
In Ubiquitous computing small embedded sensor and computing nodes are one of the main enabling technologies. System programming for such small embedded systems is a challenging task involving various hardware componen...
详细信息
ISBN:
(纸本)3540252738
In Ubiquitous computing small embedded sensor and computing nodes are one of the main enabling technologies. System programming for such small embedded systems is a challenging task involving various hardware components with different characteristics. This paper presents a file system for sensor nodes platforms providing a common organization structure and a lightweight and uniform access model for sensors and all other resources on sensor nodes. This mechanism forms an abstraction from different hardware, makes functions re-useable and simplifies the development on such systems. With ParticleFS an file system implementation on a sensor node platform is shown. As an example a telnet application running on sensor nodes was implemented demonstrating the usage of the approach for system programming on such platforms.
暂无评论