Opened 14 years ago
Closed 11 years ago
#1329 closed feature request (done)
Implement scheduling problems
Reported by: | swagner | Owned by: | abeham |
---|---|---|---|
Priority: | high | Milestone: | HeuristicLab 3.3.8 |
Component: | Problems.Scheduling | Version: | 3.3.8 |
Keywords: | Cc: |
Description
Change History (61)
comment:1 Changed 13 years ago by jhelm
- Owner changed from swagner to jhelm
- Status changed from new to accepted
- Version changed from 3.3.2 to 3.3.3
comment:2 Changed 13 years ago by jhelm
- Version changed from 3.3.3 to branch
comment:3 Changed 13 years ago by jhelm
comment:4 Changed 13 years ago by jhelm
r6041: Created empty plugin for scheduling.
comment:5 Changed 13 years ago by abeham
Any further progress or problems so far?
comment:6 Changed 13 years ago by jhelm
r6121: Implemented basic functionalities of problemdefinition, encodings and primitive operators. A GA can already be applied on the problem to compute a solution. It seems however that the current implementation isn't very efficient so the process takes some time.
comment:7 Changed 13 years ago by jhelm
r6177: Implemented PriorityRulesVector based encoding and added new operators to the JSMEncoding. Added Gantt-Charts for visualization of schedules and problems.
comment:8 Changed 13 years ago by jhelm
r6260: Implemented PermutationWithRepetition Encoding. Implemented new operators for JSM Encoding.
comment:9 Changed 13 years ago by jhelm
r6266: Did some heavy refactoring.
comment:10 Changed 13 years ago by jhelm
comment:11 Changed 13 years ago by jhelm
r6297: Added SchedulingEncoding.Views plugin.
comment:12 Changed 13 years ago by jhelm
r6364: Did some minor refactoring.
comment:13 Changed 13 years ago by abeham
- Component changed from ### Undefined ### to Problems.Scheduling
- Owner changed from jhelm to abeham
- Status changed from accepted to reviewing
comment:14 Changed 13 years ago by abeham
Unfortunately I think we'll not have the time to do a face to face review, so I'll just write my comments here.
General remarks and tips:
- Please get used to WikiFormatting for commit messages and ticket comments: A ! prevents camel case words from turning into wiki-links and we use to emphasize type names and other short code fragments by enclosing them with grave accents (`) (which also prevents them from turning into wiki-links).
- Take a look at the VS2010 extensions "Productivity Power Tools" and "PowerCommands". One of them has an option to remove and sort usings on save which you should enable. There's also an option to perform code formatting when saving which is also very useful. Also you might find the SolutionNavigator more useful than the default SolutionExplorer (so far pretty much everyone did).
- For several repetitive stuff there are code snippets available. Go to Tools > Code Snippets Manager and add the folder in trunk\tools\HL3Snippets (a restart is not required). All code snippets are prefixed with "hl3" so if you want to add the license header just type hl3license and confirm by pressing the tab key twice. The license header is automatically added at the current cursor position and you have the option to set the year (2011 is fine for now though ;-)). There are others like hl3ParameterProperty, hl3AddParameter, hl3CloneMethod, hl3CloningConstructor, hl3StorableConstructor, etc. that I use a lot. I mentioned the license header, because I found them missing here and there, please check all source files and also all designer generated source files and add them at the beginning.
HeuristicLab.Encodings.ScheduleEncoding:
- Check AssemblyInfo.frame in other projects (in the Properties folder)
- The namespace should be called HeuristicLab.Encodings.ScheduleEncoding, the -ing should be dropped from all operators (the problem is still called Scheduling though)
- Interfaces
- You placed the interfaces in a sub-namespace (.Interfaces). There are exceptions, but we don't do this and typically have only one namespace per plugin. Please place all interfaces in the plugin's root namespace. You might want to keep the concrete encodings and their operators in their own namespace though.
- IScheduleCreator should derive from both ISolutionCreator and IScheduleOperator
- IScheduleCrossover should derive from both ICrossover and IScheduleOperator.
- IScheduleManipulator should derive from both IManipulator and IScheduleOperator
- Plugin.cs.frame
- The version should be updated to 3.3.4
- The plugin dependencies are missing (the unit test PluginDependenciesTest in HeuristicLab-3.3.Tests should pass)
- ScheduleCreator
- should have ScheduleCreator as ItemName. We are aware that naming is inconsistent in HeuristicLab, but generally camel-case outweighs and you should only use spaces if it really hurts readability.
- it's strange that it implements IScheduleEncoding, it should not do that
- the parameter SchedulingSolution should be renamed to ScheduleEncoding in the abstract classes. A SchedulingSolution (this time with -ing) is something different and typically a type of the problem plugin. Compare e.g. Permutation and TSPTour, or Permutation and QAPAssignment
- The order in the operators is also typically such that parameter properties come first, then properties and then the constructor.
- ScheduleCrossover
- should also be item-named ScheduleCrossover
- should not implement IScheduleEncoding
- ScheduleDecoder
- item name
- should have the parameters ScheduleEncoding and Schedule (which is the decoded type of ScheduleEncoding)
- ScheduleManipulator
- item name and description (remove JSSP)
- parameter
- JSMEncoding
- item name (please check them all, I won't state anymore)
- storable types first
- There's no need to derive from ParameterizedNamedItem, keep it really simple for types that are cloned and used often, probably deriving from Item is enough
- It's not true that this encoding represents a solution to a JSSP as stated in the description. A solution would be a schedule, and this is just a constructive description of a schedule, of which possibly multiple schedules (=solutions) may be inferred (if there is space for interpretation). This may seem like nitpicking, but there's quite a difference. In cases where the encoding and the solution are 1:1 relationships (like in a TSP or QAP) it's possible to mix these, but in the general case there is a distinction between the encoding (often called the genotype) that is crossed and manipulated and the solution (often called the phenotype) which is evaluated.
- JSMRandomCreator
- parameter properties first
- set the ActualName of the ScheduleEncoding parameter to JobSequenceMatrix to have some distinction in the variables they create
- JSMCrossover
- again just use HeuristicLab.Encodings.ScheduleEncoding.JobSequenceMatrix as interface
- also set the ActualName of the Child and Parents parameters to JobSequenceMatrix
- the abstract method should be called Cross rather than Crossover (same for other crossovers)
- JSMJOXCrossover
- The static Cross method should be called Apply (same for other operators)
- Please add a unit test project and include unit tests for this crossover (checking the static cross method should be enough). Just build some example JSMs, define the random number sequence (look at the TestRandom class that I have written some other crossover unit tests with) and the outcome and make sure that everything is fine. If you have some examples from the literature you can include these, otherwise think of some examples yourself. This also holds for other crossovers (where this can be done with a reasonable time-effort).
- JSMSXXCrossover
- Please remove comments that just hide old code
- JSMManipulator
- Again ScheduleEncodingParameter.ActualName = "JobSequenceMatrix"
- The following code is probably wrong, it doesn't matter if you execute it once or 5 times only the last manipulation operation remains. Manipulate() should not return a clone, but directly manipulate the encoding. The caller is responsible for cloning in case he needs the original after the operation. Also hard-coded values like "5" should better be exposed as, in this case, a ValueLookupParameter<IntValue> (Why ValueLookup? - So that you can also place the value in the scope and dynamically adjust it by some other operation should this be of interest. If you clear the Value of a ValueLookupParameter it will look for the value in the execution context hierachy and the scope tree).
JSMEncoding solution = SchedulingSolutionParameter.ActualValue; int nrOfMutations = RandomParameter.ActualValue.Next(5) + 1; for (int i = 0; i < nrOfMutations; i++ ) SchedulingSolutionParameter.ActualValue = Manipulate(RandomParameter.ActualValue, solution as JSMEncoding);
- JSM*Manipulator
- Move the actual manipulation code into static methods
- Again unit tests would be nice
- PRV and PWR
- I hope the comments on JSM provided you with enough information to change these accordingly
- Resource
- All properties that should be stored (e.g. Index) need the [Storable] attribute
- I wouldn't use IntValue for index, but just an int
- Schedule
- the item name should just read Schedule
- Should have much more virtual methods, this class will be overwritten for specific scheduling problems which may calculate !Makespan and the like differently
- the constructor should accept an int instead of an IntValue
- put storable and clonding constructor as well as clone method below the properties
- Matter of Taste, but the property Makespan does some calculation and should probably rather be a virtual method CalculateMakespan() to make it more obvious that there's computation time involved
- Quality doesn't need to have an initial value, it can be null indicating that the quality has not yet been calculated. If you assign a new QualityValue() in the constructor you can't differ between a quality of 0 and one that has not yet been evaluated.
- ScheduledTask
- Probably some [Storable] attributes missing
- Again I would use double and int instead of IntValue and DoubleValue in some fields.
HeuristicLab.Encodings.ScheduleEncoding.Views:
- Plugin dependencies and version information
- Check AssemblyInfo.frame in other projects (in the Properties folder)
- ScheduleView
- FillGanttChart would be better called RedrawGanttChart
- GanttChart
- again a reminder to check license headers in .cs and .Designer.cs files
- think about renaming this to e.g. SimpleGanttChart and move it to HeuristicLab.Visualization.ChartControlsExtensions
comment:15 Changed 13 years ago by abeham
HeuristicLab.Problems.Scheduling:
- There's a missing file called IndexedTaskList.cs. Please remove it from the project or add it to source control
- Job, Task
- [Storable] attributes missing
- please unify formatting for properties, I like the one liner when the get and set accessor is not explicitly implemented
- I would again use the .NET primitive types in some cases
- JobShopSchedulingProblem
- Implement IStorableContent so that it can get saved
- Use the appropriate item image property
- Make sure to react on OnEvaluatorChanged appropriately
- Parameters are cloned by the ParameterizedNamedItem class, they don't need to be cloned in the problem again
- Please add a reference to whoever introduced the problem in the item's description
- You need to listen on changes to the ScheduleEncodingParameter's ActualName of the SolutionCreator (yes, the naming is not consistent). If that name changes, you need to adapt all relevant operators (evaluator, crossover, manipulator) to the new name.
so much for today
comment:16 Changed 13 years ago by jhelm
- Owner changed from abeham to jhelm
- Status changed from reviewing to assigned
comment:17 Changed 13 years ago by jhelm
r6406: Applied suggestions from codereview. Added unit-tests. Renamed encoding-project.
comment:18 Changed 13 years ago by jhelm
r6412: Did some minor changes affecting datatypes.
comment:19 Changed 13 years ago by jhelm
r6414: Fixed a bug in PRVCrossover-Operators.
comment:20 Changed 13 years ago by jhelm
r6475: Added DirectSchedule-Classes for optimization with the direct-schedule encoding.
comment:21 Changed 13 years ago by gkronber
Please do not check in Plugin.cs and AssemblyInfo.cs files. They are autogenerated. Only the template files Plugin.frame and AssemblyInfo.frame should be under version control.
comment:22 Changed 13 years ago by jhelm
r6482: Applied some changes to the ScheduleView. Added TaskNr properties to ScheduledTask to make specific selection of tasks in the view possible. Deleted AssemblyInfo.cs and Plugin.cs files.
comment:23 Changed 13 years ago by swagner
- Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.6
- Owner changed from jhelm to swagner
- Status changed from assigned to reviewing
comment:24 Changed 13 years ago by mkommend
- Owner changed from swagner to mkommend
- Status changed from reviewing to assigned
comment:25 Changed 13 years ago by mkommend
- Status changed from assigned to accepted
The scheduling branch should be prepared for inclusion in the build process.
comment:26 Changed 13 years ago by mkommend
- Milestone changed from HeuristicLab 3.3.6 to HeuristicLab 3.3.x Backlog
comment:27 Changed 13 years ago by mkommend
r7114: Adapted scheduling branch to new repository layout.
comment:28 Changed 13 years ago by mkommend
- Owner changed from mkommend to gkronber
- Status changed from accepted to assigned
comment:29 Changed 13 years ago by gkronber
- added a solution file
- added missing overrides for GetHashCode()
- removed tautological if-conditions
- adapted prebuildevent script
- added the build script
comment:30 Changed 13 years ago by gkronber
- removed project HeuristicLab
- removed a few references but I'm sure there are many unnecessary references left over!
- added plugin dependencies
comment:31 Changed 13 years ago by gkronber
r7118: fixed typo in plugin dependency
comment:32 Changed 12 years ago by gkronber
- Status changed from assigned to accepted
comment:33 Changed 12 years ago by gkronber
The scheduling add-on is available for download as a daily build on the addons page. http://dev.heuristiclab.com/trac/hl/core/wiki/BranchesDailyBuilds
comment:34 Changed 12 years ago by gkronber
- updated copy-right year
- trimmed assembly and plugin references
- removed x86 and x64 build configurations
comment:35 Changed 12 years ago by gkronber
I think this plugin would be ready for integration into the HL trunk.
comment:36 Changed 12 years ago by gkronber
r8757: integrated Scheduling branch into trunk
comment:37 Changed 12 years ago by gkronber
r8758: deleted unnecessarily copied files
comment:38 Changed 12 years ago by gkronber
- Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.8
- Version changed from branch to 3.3.7
comment:39 Changed 12 years ago by gkronber
- Owner changed from gkronber to abeham
- Status changed from accepted to reviewing
Please review trunk integration r8757:8759
comment:40 Changed 12 years ago by gkronber
- Owner changed from abeham to gkronber
- Status changed from reviewing to assigned
comment:41 Changed 12 years ago by gkronber
- Owner changed from gkronber to abeham
- Status changed from assigned to reviewing
comment:42 Changed 12 years ago by ascheibe
r8769 fixed prebuild events so that they work with Mono
comment:43 Changed 12 years ago by ascheibe
r8772 another fix for the prebuild events for Mono (missed the Encoding)
comment:44 Changed 12 years ago by ascheibe
r8780 added RAPGA JSSP sample
comment:45 Changed 12 years ago by jkarder
r8785: corrected RAPGA JSSP sample test
comment:46 Changed 12 years ago by ascheibe
r8788 signed Scheduling Problem View project
comment:47 Changed 12 years ago by ascheibe
r8800 changed references in scheduling projects to project references
comment:48 Changed 12 years ago by abeham
- Status changed from reviewing to assigned
comment:49 Changed 12 years ago by abeham
- Status changed from assigned to accepted
comment:50 Changed 12 years ago by abeham
- Added JSSPData class to problem instances
- Added problem instance provider for some ORLIB JSSP instances (abz, ft, la01-20)
- Adapted JSSP to load and export jssp problems
- Adapted JSSP problem view to derive from ProblemView
- Added static methods to MakespanEvaluator and MeanTardinessEvaluator
- Fixed a bug in PRVUniformOnePositionManipulator
comment:51 Changed 12 years ago by abeham
- Removed unnecessary DueDates parameter
- Changed ValueParameter to FixedValueParameter for Jobs and Resources
- Made Job and Task INotifyPropertyChanged
- Added a JobView and TaskView
comment:52 Changed 12 years ago by abeham
- Moved decoders and evaluators from encoding to problem
- Removed unnecessary state variables in operators
- Introduced parameters in interfaces and added wiring code
- Removed ConcreteScheduleManipulator as it does not perform any manipulation
- Made ErrorPolicy and ForcingStrategy configurable and added views for them
- Renamed the SchedulingEvaluationAlgorithm and also converted the AlgorithmOperator to a SingleSuccessorOperator
- Fixed Plugin- and AssemblyFileVersion
- Added missing license headers
comment:53 follow-up: ↓ 57 Changed 12 years ago by abeham
- Owner changed from abeham to jkarder
- Status changed from accepted to assigned
I have one more bigger item on the todo list:
- PRV and PWR encoding should be replaced by IntArray
But I will leave this as it is as for now. The reason is that I think the priority rules encoding should be more flexible and should be overhauled to a bigger degree.
Also, I took the freedom to make some breaking changes during the last commits since I think nobody used it seriously so far. Therefore, I'd like to ask if you could recreate the JSSP sample.
comment:54 Changed 12 years ago by abeham
- Fixed failed test case (mutation is now working)
- Removed TestRandom and used the one in the Tests namespace
- Corrected namespaces
comment:55 Changed 12 years ago by jkarder
- Status changed from assigned to accepted
comment:56 Changed 12 years ago by jkarder
- recreated RAPGA JSSP sample
- corrected RAPGA JSSP sample test
comment:57 in reply to: ↑ 53 Changed 12 years ago by jkarder
- Owner changed from jkarder to abeham
- Status changed from accepted to assigned
Replying to abeham:
I have one more bigger item on the todo list:
- PRV and PWR encoding should be replaced by IntArray
But I will leave this as it is as for now. The reason is that I think the priority rules encoding should be more flexible and should be overhauled to a bigger degree.
Also, I took the freedom to make some breaking changes during the last commits since I think nobody used it seriously so far. Therefore, I'd like to ask if you could recreate the JSSP sample.
Thanks for overhauling the implementation. It seems that you have also fixed the problem of the sample test yielding different results on different machines - at least ascheibe and I now obtain the same results.
comment:58 Changed 12 years ago by abeham
- Status changed from assigned to reviewing
comment:59 Changed 12 years ago by abeham
- Status changed from reviewing to readytorelease
comment:60 Changed 12 years ago by abeham
r8911: (Hopefully) fixed a problem with ziplib reference
comment:61 Changed 11 years ago by swagner
- Resolution set to done
- Status changed from readytorelease to closed
- Version changed from 3.3.7 to 3.3.8
r6040: Created branch for scheduling problems.