Heuristics for Job-Shop Scheduling
Two methods of obtaining approximate solutions to the classic General Job-shop Scheduling Program are investigated. The first method is iterative. A sampling of the solution space is used to decide which of a collection of space pruning constraints are consistent with "good" schedule...
| Main Author: | |
|---|---|
| Language: | en_US |
| Published: |
2004
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/6847 |
| _version_ | 1811091326357209088 |
|---|---|
| author | Pasch, Kenneth Alan |
| author_facet | Pasch, Kenneth Alan |
| author_sort | Pasch, Kenneth Alan |
| collection | MIT |
| description | Two methods of obtaining approximate solutions to the classic General Job-shop Scheduling Program are investigated. The first method is iterative. A sampling of the solution space is used to decide which of a collection of space pruning constraints are consistent with "good" schedules. The selected space pruning constraints are then used to reduce the search space and the sampling is repeated. This approach can be used either to verify whether some set of space pruning constraints can prune with discrimination or to generate solutions directly. Schedules can be represented as trajectories through a Cartesian space. Under the objective criteria of Minimum maximum Lateness family of "good" schedules (trajectories) are geometric neighbors (reside with some "tube") in this space. This second method of generating solutions takes advantage of this adjacency by pruning the space from the outside in thus converging gradually upon this "tube." One the average this methods significantly outperforms an array of the Priority Dispatch rules when the object criteria is that of Minimum Maximum Lateness. It also compares favorably with a recent relaxation procedure. |
| first_indexed | 2024-09-23T15:00:41Z |
| id | mit-1721.1/6847 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:00:41Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/68472019-04-10T14:25:10Z Heuristics for Job-Shop Scheduling Pasch, Kenneth Alan scheduling job-shop heuristic geometric Two methods of obtaining approximate solutions to the classic General Job-shop Scheduling Program are investigated. The first method is iterative. A sampling of the solution space is used to decide which of a collection of space pruning constraints are consistent with "good" schedules. The selected space pruning constraints are then used to reduce the search space and the sampling is repeated. This approach can be used either to verify whether some set of space pruning constraints can prune with discrimination or to generate solutions directly. Schedules can be represented as trajectories through a Cartesian space. Under the objective criteria of Minimum maximum Lateness family of "good" schedules (trajectories) are geometric neighbors (reside with some "tube") in this space. This second method of generating solutions takes advantage of this adjacency by pruning the space from the outside in thus converging gradually upon this "tube." One the average this methods significantly outperforms an array of the Priority Dispatch rules when the object criteria is that of Minimum Maximum Lateness. It also compares favorably with a recent relaxation procedure. 2004-10-20T20:02:14Z 2004-10-20T20:02:14Z 1988-01-01 AITR-1036 http://hdl.handle.net/1721.1/6847 en_US AITR-1036 163 p. 13869314 bytes 5230492 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | scheduling job-shop heuristic geometric Pasch, Kenneth Alan Heuristics for Job-Shop Scheduling |
| title | Heuristics for Job-Shop Scheduling |
| title_full | Heuristics for Job-Shop Scheduling |
| title_fullStr | Heuristics for Job-Shop Scheduling |
| title_full_unstemmed | Heuristics for Job-Shop Scheduling |
| title_short | Heuristics for Job-Shop Scheduling |
| title_sort | heuristics for job shop scheduling |
| topic | scheduling job-shop heuristic geometric |
| url | http://hdl.handle.net/1721.1/6847 |
| work_keys_str_mv | AT paschkennethalan heuristicsforjobshopscheduling |