Browse Prior Art Database

Constraint-Directed Search: A Case Study of Job-Shop Scheduling

IP.com Disclosure Number: IPCOM000148116D
Original Publication Date: 1983-Dec-13
Included in the Prior Art Database: 2007-Mar-29

Publishing Venue

Software Patent Institute

Related People

Fox, Mark S.: AUTHOR [+2]

Abstract

Const raint-Directed sea&: 1 A Case Study of Job-Shop Schedulind I Ri.4DiNCI ROOM --, Mark S MFUTER $@iE&:C$: ,BEP&R'TMENT yp'&~ ,,jN{gi'~RSj-j"y 1 v . 13 Deccmber 1983 Computer Science Department Carnegie-Mellon UniversityPittsburgh, Pennsylvania 15213 Submitted in panial fulfillment of the rcquircments for the degree of Doctor of Philosophy 1 Copyright 1983 Mark S. Fox I This research was sponsored, in part. by the Air Forcc Office of Scicnti c Research under contract F49620-82-K0017. and the Westinghouse Corporation. fi MARK S. FOX PAGE l Table of Contents 1. Introduction 1.1. The Scheduling Problem 1.1.1. Constraint Categories 1.2. Constraint-Directed Search: Issues and Objectives 1.3. Thesis Summary 1.3.1. Modeling 1.3.2. Constraints 1.3.3. Scheduling 1.3.4. Analysis 1.3.5. Conclusions 2. Review 2.1. lntroduction 2.2. Management Science 2.3. Artificial Intelligence 2.4. Relationship to Previous Research 3. lSlS Modeling System

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 3% of the total text.

Page 1 of 208

Const raint-Directed sea&: 1

A Case Study of Job-Shop Schedulind

I

     Ri.4DiNCI ROOM --, Mark S @ ~ @ ~ MFUTER $@iE&:C$: ,BEP&R'TMENT

v .

13 Deccmber 1983

Computer Science Department Carnegie-Mellon University
Pittsburgh, Pennsylvania 15213

Submitted in panial fulfillment of the rcquircments for the degree of Doctor of Philosophy 1

Copyright @ 1983 Mark S. Fox

This research was sponsored, in part. by the Air Forcc Office of Scicnti c Research under contract F49620-82-K0017. and the Westinghouse Corporation.

-

yp'&~

,,jN{gi'~RSj-j"y 1

I

fi

[This page contains 1 picture or other non-text object]

Page 2 of 208

[This page contains 1 picture or other non-text object]

Page 3 of 208

[This page contains 1 picture or other non-text object]

Page 4 of 208

[This page contains 1 picture or other non-text object]

Page 5 of 208

MARK S. FOX

PAGE l

Table of Contents

1. Introduction
1.1. The Scheduling Problem
1.1.1. Constraint Categories
1.2. Constraint-Directed Search: Issues and Objectives
1.3. Thesis Summary
1.3.1. Modeling
1.3.2. Constraints
1.3.3. Scheduling
1.3.4. Analysis
1.3.5. Conclusions
2. Review

2.1. lntroduction
2.2. Management Science
2.3. Artificial Intelligence
2.4.

Relationship to Previous Research
3. lSlS Modeling System

3.1. lntroduction
3.2.

Layer 1 : Structure
3.2.1. Schema Syntax
3.2.2. Meta-Information
3.2.3. Inheritance
3.3. Level 2: Basic Semantics
3.3.1 . Classes, Sets and Instances
3.3.2. Attributes, Parts and Structure
3.3.3. Abstraction
3.4. Layer 3: World Model
3.4;1. State/Acts
3.4.2. Time
3.4.3. Causality
3.4.4. States Rzvisted: Possession and Manifestations
3.4.5. Composite States and Parallelism
3.4.6. Repetition
3.4.7. Time Revisited: The Future and the Past
3.4.8.

Scheduling Goals
3.5. Layer I: Domain Semantics
3.5.1. Operations
3.5.2. Reservations
3.5.3. Products
5.5.4. Orders

TABLE OF CON'TENTS

[This page contains 1 picture or other non-text object]

Page 6 of 208

PAGE I1

3.6. Schedule
3.7. Model Interpretation/Sirnuiotion
3.8. Conclusion
4. Constraints
4.1. lntroduction
4.2. Structural Constraints
4.2.1 . Range Constraint
4.2.2. Relation Constraint
4.2.3. Schema Constraint
4.3. Relaxations and Preferences
4.3.1. Relaxation Specification
4.3.2. Relaxation Generation and Testing
4.4. lmportance
4.5. Interactions
4.6. Obligation
4.6.1. Duration
4.6.2. Consistency
4.6.3. Residency
4.6.4. Context
4.6.5. Obligation Resolution
4.7. Generat'ion
4.8. The Constraint Schema
4.9. Examples
4.9.1. Predicate Range Constrairtt
4.9.2. Discrete Range Constraini
4.9.3. Continuous Range Constraint
4.9.4. Meta-constraints: Importance Partitioning
4.1 0.
Conclusion

4.1 1. Appendix: Predicate Specification
5. Constraint-Directed Scheduling
5.1. lntroduction
5.2. lSlS ProSlem-Solving Architecture Overview
5.3. Level 1: Lot Selection
5.4. Level 2: Capacity-Based Analysis
5.4.1. Pre-Search Analysis
5.4.2. Search: Capaci...