ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Resource Constraints for Preemptive Job-shop Scheduling (1998)
    Springer
    Constraints 3 (1998), S. 263-287 
    Details
    ISSN: 1572-9354
    Keywords: constraint propagation ; preemptive scheduling ; resource constraints ; timetables ; disjunctive constraints ; edge-finding ; network flows ; job-shop scheduling
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper presents an experimental study of constraint propagation algorithms for preemptive scheduling. We propose generalizations of non-preemptive constraint propagation techniques (based on timetables, on disjunctive constraints, and on edge-finding) to preemptive and “mixed” problems, i.e., problems in which some activities can be interrupted and some cannot. Another approach relies on incremental flow-based techniques. We theoretically compare these approaches and present an experimental comparison based on a branch and bound procedure for the preemptive variant of the job-shop scheduling problem. We show that both edge-finding and flow-based techniques allow the resolution of hard problem instances, including the preemptive variant of the famous FT10.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009723704757
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Constraint Propagation and Decomposition Techniques for Highly Disjunctive and Highly Cumulative Project Scheduling Problems (2000)
    Springer
    Constraints 5 (2000), S. 119-139 
    Details
    ISSN: 1572-9354
    Keywords: resource-constrained project scheduling ; cumulative scheduling ; disjunctive scheduling ; deduction rules ; constraint propagation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In recent years, constraint satisfaction techniques have been successfully applied to “disjunctive” scheduling problems, i.e., scheduling problems where each resource can execute at most one activity at a time. Less significant and less generally applicable results have been obtained in the area of “cumulative” scheduling. Multiple constraint propagation algorithms have been developed for cumulative resources but they tend to be less uniformly effective than their disjunctive counterparts. Different problems in the cumulative scheduling class seem to have different characteristics that make them either easy or hard to solve with a given technique. The aim of this paper is to investigate one particular dimension along which problems differ. Within the cumulative scheduling class, we distinguish between “highly disjunctive” and “highly cumulative” problems: a problem is highly disjunctive when many pairs of activities cannot execute in parallel, e.g., because many activities require more than half of the capacity of a resource; on the contrary, a problem is highly cumulative if many activities can effectively execute in parallel. New constraint propagation and problem decomposition techniques are introduced with this distinction in mind. This includes an O(n2) “edge-finding” algorithm for cumulative resources (where n is the number of activities requiring the same resource) and a problem decomposition scheme which applies well to highly disjunctive project scheduling problems. Experimental results confirm that the impact of these techniques varies from highly disjunctive to highly cumulative problems. In the end, we also propose a refined version of the “edge-finding” algorithm for cumulative resources which, despite its worst case complexity in O(n3) , performs very well on highly cumulative instances.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009822502231
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Heuristic Control of a Constraint-Based Algorithm for the Preemptive Job-Shop Scheduling Problem (1999)
    Springer
    Journal of heuristics 5 (1999), S. 305-325 
    Details
    ISSN: 1572-9397
    Keywords: preemptive scheduling ; job-shop scheduling ; constraint programming ; constraint propagation ; resource constraints ; timetables ; edge-finding ; limited discrepancy search ; depth-bounded discrepancy search
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In the recent years, constraint programming has been applied to a wide variety of academic and industrial non-preemptive scheduling problems, i.e., problems in which activities cannot be interrupted. In comparison, preemptive scheduling problems have received almost no attention from both the Operations Research and the Artificial Intelligence community. Motivated by the needs of a specific application, we engaged in a study of the applicability of constraint programming techniques to preemptive scheduling problems. This paper presents the algorithms we developed and the results we obtained on the preemptive variant of the famous “job-shop scheduling problem.” Ten heuristic search strategies, combined with two different constraint propagation techniques, are presented, and compared using two well-known series of job-shop scheduling instances from the literature. The best combination, which relies on “limited discrepancy search” and on “edge-finding” techniques, is shown to provide excellent solutions to the preemptive job-shop scheduling problem. A mean relative distance to the optimal solution of 0.32% is achieved in five minutes, on instances with 10 jobs and 10 machines (100 activities).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009613717770
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...