Free cookie consent management tool by TermsFeed Policy Generator

source: branches/3.1/sources/HeuristicLab.Scheduling.JSSP/ScheduleTree.cs @ 3508

Last change on this file since 3508 was 385, checked in by mkofler, 16 years ago

Adjusted ScheduleTree and TimeSlot to allow preemptive scheduling

File size: 7.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2008 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Text;
25using System.Xml;
26using HeuristicLab.Data;
27using HeuristicLab.Core;
28
29namespace HeuristicLab.Scheduling.JSSP {
30
31  public class ScheduleTreeNode {
32    private TimeSlot data;
33    private ScheduleTreeNode left;
34    private ScheduleTreeNode right;
35    private ScheduleTreeNode parent;
36
37    public ScheduleTreeNode(TimeSlot t) {
38      data = t;
39    }
40
41    public ScheduleTreeNode Left {
42      get { return left; }
43      set { left = value; }
44    }
45
46    public ScheduleTreeNode Right {
47      get { return right; }
48      set { right = value; }
49    }
50
51    public ScheduleTreeNode Parent {
52      get { return parent; }
53      set { parent = value; }
54    }
55
56    public void SetLeft(ScheduleTreeNode child) {
57      this.Left = child;
58      child.Parent = this;
59    }
60
61    public void SetRight(ScheduleTreeNode child) {
62      this.Right = child;
63      child.Parent = this;
64    }
65
66    public TimeSlot Data {
67      get { return data; }
68      set { data = value; }
69    }
70  }
71
72  public class ScheduleTree : StorableBase {
73    private ScheduleTreeNode root;
74
75    public ScheduleTreeNode Root {
76      get { return root; }
77    }
78
79    private int timespan;
80    public int Timespan {
81      get { return timespan; }
82    }
83
84    public ScheduleTree(int timespan) {
85      root = new ScheduleTreeNode(new TimeSlot(0, timespan));
86      this.timespan = timespan;
87    }
88
89    public ScheduleTree() : this(10000) { }
90
91    private int InsertOperation(Operation op) {
92      return Insert(this.Root, op);
93    }
94
95    private int InsertOperation(TimeSlot t) {
96      return Insert(this.Root, t.operation);
97    }
98
99    // ToDo: Rewrite code! (not efficient)
100    public int Insert(Operation op) {
101      foreach(ScheduleTreeNode node in this.InOrder) {
102        int start = Math.Max(node.Data.start, op.Start);
103        if((IsLeaf(node)) && (FitsIntoEmptySlot(node.Data, start, op.Duration))) {
104          op.Start = start;
105          return Insert(node, op);
106        }
107      }
108      return -1;
109    }
110
111    private bool FitsIntoEmptySlot(TimeSlot slot, int start, int duration) {
112      // beware of operations with processing time zero --> check operation != null
113      return ((slot.free >= duration) && (slot.start <= start) && (slot.end >= start + duration) && (slot.operation == null));
114    }
115
116    private void UpdateMaxFreeSlot(ScheduleTreeNode slot) {
117      while(slot != null) {
118        if(!IsLeaf(slot)) {
119          int newMax = Math.Max(slot.Left.Data.maxFreeSlot, slot.Right.Data.maxFreeSlot);
120          slot.Data.free = slot.Left.Data.free + slot.Right.Data.free;
121          slot.Data.maxFreeSlot = newMax;
122        }
123        slot = slot.Parent;
124      }
125    }
126
127    public int Insert(ScheduleTreeNode slot, Operation op) {
128      if (op == null) {
129        return -1;
130      }
131      int end = op.Start + op.Duration;;
132      if(slot.Data.maxFreeSlot < op.Duration) {
133        return -1;
134      }
135      if(IsLeaf(slot)) {
136        // fits exactly into slot; beware of operations with processing time 0 --> check operation != null
137        if((slot.Data.start == op.Start) && (slot.Data.end == end) && (slot.Data.operation == null)) {
138          slot.Data = new TimeSlot(op);
139          UpdateMaxFreeSlot(slot);
140          return op.Start;
141        }
142        // empty slot before op.
143        if(slot.Data.start < op.Start) {
144          ScheduleTreeNode empty1 = new ScheduleTreeNode(new TimeSlot(slot.Data.start, op.Start));
145          slot.SetLeft(empty1);
146          if(slot.Data.end > end) {
147            ScheduleTreeNode empty2 = new ScheduleTreeNode(new TimeSlot(op.Start, slot.Data.end));
148            slot.SetRight(empty2);
149            return Insert(empty2, op);
150          } else {
151            slot.SetRight(new ScheduleTreeNode(new TimeSlot(op)));
152            UpdateMaxFreeSlot(slot);
153            return op.Start;
154          }
155        }
156        // empty after op.
157        if(slot.Data.end > end) {
158          ScheduleTreeNode occupied = new ScheduleTreeNode(new TimeSlot(op));
159          ScheduleTreeNode empty2 = new ScheduleTreeNode(new TimeSlot(end, slot.Data.end));
160          slot.SetRight(empty2);
161          slot.SetLeft(occupied);
162          UpdateMaxFreeSlot(slot);
163          return op.Start;
164        }
165      } else {
166        if(slot.Left.Data.end < end) {
167          return Insert(slot.Right, op);
168        } else {
169          return Insert(slot.Left, op);
170        }
171      }
172      return -1;
173    }
174
175    public bool IsLeaf(ScheduleTreeNode slot) {
176      return ((slot.Right == null) && (slot.Left == null));
177    }
178
179    public ScheduleTreeNode GetFirstNode() { // left-most slot
180      ScheduleTreeNode node = root;
181      while (node.Left != null) {
182        node = node.Left;
183      }
184      return node;
185    }
186
187    public ScheduleTreeNode GetLastNode() { // right-most slot
188      ScheduleTreeNode node = root;
189      while (node.Right != null) {
190        node = node.Right;
191      }
192      return node;
193    }
194
195    public override string ToString() {
196      StringBuilder builder = new StringBuilder();
197      foreach(ScheduleTreeNode node in this.InOrder) {
198        if(IsLeaf(node)) {
199          builder.Append(node.Data.ToString());
200          builder.Append(";");
201        }
202      }
203      return builder.ToString();
204    }
205
206    #region IEnumerable Members
207    public IEnumerable<ScheduleTreeNode> InOrder {
208      get { return ScanInOrder(root); }
209    }
210
211    IEnumerable<ScheduleTreeNode> ScanInOrder(ScheduleTreeNode root) {
212      if(root.Left != null) {
213        foreach(ScheduleTreeNode node in ScanInOrder(root.Left)) {
214          yield return node;
215        }
216      }
217      yield return root;
218      if(root.Right != null) {
219        foreach(ScheduleTreeNode node in ScanInOrder(root.Right)) {
220          yield return node;
221        }
222      }
223    }
224    #endregion
225
226    #region IStorable Members
227    public override XmlNode GetXmlNode(string name, XmlDocument document, IDictionary<Guid,IStorable> persistedObjects) {
228      XmlNode node = base.GetXmlNode(name, document, persistedObjects);
229      node.InnerText = this.ToString();
230      return node;
231    }
232
233    public override void Populate(XmlNode node, IDictionary<Guid,IStorable> restoredObjects) {
234      base.Populate(node, restoredObjects);
235      string[] tokens = node.InnerText.Split(';');
236      for(int i = 0; i < tokens.Length - 1; i++) {
237        TimeSlot t = new TimeSlot(tokens[i]);
238        if(t.job > -1) {
239          this.InsertOperation(t);
240        }
241      }
242    }
243
244    public override object Clone(IDictionary<Guid, object> clonedObjects) {
245      ScheduleTree clone = new ScheduleTree(timespan);
246      clonedObjects.Add(Guid, clone);
247      foreach (ScheduleTreeNode node in this.InOrder) {
248        if (IsLeaf(node) && (node.Data.job > -1)) {
249          clone.InsertOperation(node.Data);
250        }
251      }
252      return clone;
253    }
254
255    #endregion
256  }
257}
Note: See TracBrowser for help on using the repository browser.