Implement scheduling problems

[jhelm]

r6040: Created branch for scheduling problems.

[jhelm]

r6041: Created empty plugin for scheduling.

[abeham]

Any further progress or problems so far?

[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.

[jhelm]

r6177: Implemented PriorityRulesVector based encoding and added new operators to the JSMEncoding. Added Gantt-Charts for visualization of schedules and problems.

[jhelm]

r6260: Implemented PermutationWithRepetition Encoding. Implemented new operators for JSM Encoding.

[jhelm]

r6266: Did some heavy refactoring.

[jhelm]

r6293 - r6294: Did some heavy refactoring after "code-review meeting". Added Encodings.SchedulingEncoding plugin to store encodings used in scheduling problems.

[jhelm]

r6297: Added SchedulingEncoding.Views plugin.

[jhelm]

r6364: Did some minor refactoring.

[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

[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

[jhelm]

r6406: Applied suggestions from codereview. Added unit-tests. Renamed encoding-project.

[jhelm]

r6412: Did some minor changes affecting datatypes.

[jhelm]

r6414: Fixed a bug in PRVCrossover-Operators.

[jhelm]

r6475: Added DirectSchedule-Classes for optimization with the direct-schedule encoding.

[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.

[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.

[mkommend]

The scheduling branch should be prepared for inclusion in the build process.

[mkommend]

r7114: Adapted scheduling branch to new repository layout.

[gkronber]

r7116:

• added a solution file
• added missing overrides for GetHashCode()
• removed tautological if-conditions
• adapted prebuildevent script
• added the build script

[gkronber]

r7117:

• removed project HeuristicLab
• removed a few references but I'm sure there are many unnecessary references left over!
• added plugin dependencies

[gkronber]

r7118: fixed typo in plugin dependency

[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

[gkronber]

r8603:

• updated copy-right year
• trimmed assembly and plugin references
• removed x86 and x64 build configurations

[gkronber]

I think this plugin would be ready for integration into the HL trunk.

[gkronber]

r8757: integrated Scheduling branch into trunk

[gkronber]

r8758: deleted unnecessarily copied files

[gkronber]

Please review trunk integration r8757:8759

[ascheibe]

r8769 fixed prebuild events so that they work with Mono

[ascheibe]

r8772 another fix for the prebuild events for Mono (missed the Encoding)

[ascheibe]

r8780 added RAPGA JSSP sample

[jkarder]

r8785: corrected RAPGA JSSP sample test

[ascheibe]

r8788 signed Scheduling Problem View project

[ascheibe]

r8800 changed references in scheduling projects to project references

[abeham]

r8882:

• 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

[abeham]

r8886:

• Removed unnecessary DueDates parameter
• Changed ValueParameter to FixedValueParameter for Jobs and Resources
• Made Job and Task INotifyPropertyChanged
• Added a JobView and TaskView

[abeham]

r8887:

• 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

[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.

[abeham]

r8888:

• Fixed failed test case (mutation is now working)
• Removed TestRandom and used the one in the Tests namespace
• Corrected namespaces

[jkarder]

r8891:

• recreated RAPGA JSSP sample
• corrected RAPGA JSSP sample test

[jkarder]

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.

[abeham]

r8911: (Hopefully) fixed a problem with ziplib reference