Opened 7 years ago

Closed 4 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 6 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 6 years ago by jhelm

  • Version changed from 3.3.3 to branch

comment:3 Changed 6 years ago by jhelm

r6040: Created branch for scheduling problems.

comment:4 Changed 6 years ago by jhelm

r6041: Created empty plugin for scheduling.

comment:5 Changed 6 years ago by abeham

Any further progress or problems so far?

comment:6 Changed 6 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.

Last edited 6 years ago by jhelm (previous) (diff)

comment:7 Changed 6 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 6 years ago by jhelm

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

comment:9 Changed 6 years ago by jhelm

r6266: Did some heavy refactoring.

comment:10 Changed 6 years ago by jhelm

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

comment:11 Changed 6 years ago by jhelm

r6297: Added SchedulingEncoding.Views plugin.

comment:12 Changed 6 years ago by jhelm

r6364: Did some minor refactoring.

comment:13 Changed 6 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 6 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 6 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 6 years ago by jhelm

  • Owner changed from abeham to jhelm
  • Status changed from reviewing to assigned

comment:17 Changed 6 years ago by jhelm

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

comment:18 Changed 6 years ago by jhelm

r6412: Did some minor changes affecting datatypes.

comment:19 Changed 6 years ago by jhelm

r6414: Fixed a bug in PRVCrossover-Operators.

comment:20 Changed 6 years ago by jhelm

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

comment:21 Changed 6 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 6 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 6 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 6 years ago by mkommend

  • Owner changed from swagner to mkommend
  • Status changed from reviewing to assigned

comment:25 Changed 6 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 6 years ago by mkommend

  • Milestone changed from HeuristicLab 3.3.6 to HeuristicLab 3.3.x Backlog

comment:27 Changed 6 years ago by mkommend

r7114: Adapted scheduling branch to new repository layout.

comment:28 Changed 6 years ago by mkommend

  • Owner changed from mkommend to gkronber
  • Status changed from accepted to assigned

comment:29 Changed 6 years ago by gkronber

r7116:

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

comment:30 Changed 6 years ago by gkronber

r7117:

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

comment:31 Changed 6 years ago by gkronber

r7118: fixed typo in plugin dependency

comment:32 Changed 5 years ago by gkronber

  • Status changed from assigned to accepted

comment:33 Changed 5 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 5 years ago by gkronber

r8603:

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

comment:35 Changed 5 years ago by gkronber

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

comment:36 Changed 5 years ago by gkronber

r8757: integrated Scheduling branch into trunk

comment:37 Changed 5 years ago by gkronber

r8758: deleted unnecessarily copied files

comment:38 Changed 5 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 5 years ago by gkronber

  • Owner changed from gkronber to abeham
  • Status changed from accepted to reviewing

Please review trunk integration r8757:8759

Last edited 5 years ago by gkronber (previous) (diff)

comment:40 Changed 5 years ago by gkronber

  • Owner changed from abeham to gkronber
  • Status changed from reviewing to assigned

comment:41 Changed 5 years ago by gkronber

  • Owner changed from gkronber to abeham
  • Status changed from assigned to reviewing

comment:42 Changed 5 years ago by ascheibe

r8769 fixed prebuild events so that they work with Mono

comment:43 Changed 5 years ago by ascheibe

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

comment:44 Changed 5 years ago by ascheibe

r8780 added RAPGA JSSP sample

comment:45 Changed 5 years ago by jkarder

r8785: corrected RAPGA JSSP sample test

comment:46 Changed 5 years ago by ascheibe

r8788 signed Scheduling Problem View project

comment:47 Changed 5 years ago by ascheibe

r8800 changed references in scheduling projects to project references

comment:48 Changed 5 years ago by abeham

  • Status changed from reviewing to assigned

comment:49 Changed 5 years ago by abeham

  • Status changed from assigned to accepted

comment:50 Changed 5 years ago by 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

comment:51 Changed 5 years ago by abeham

r8886:

  • 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 5 years ago by 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

comment:53 follow-up: Changed 5 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 5 years ago by abeham

r8888:

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

comment:55 Changed 5 years ago by jkarder

  • Status changed from assigned to accepted

comment:56 Changed 5 years ago by jkarder

r8891:

  • recreated RAPGA JSSP sample
  • corrected RAPGA JSSP sample test

comment:57 in reply to: ↑ 53 Changed 5 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 5 years ago by abeham

  • Status changed from assigned to reviewing

comment:59 Changed 5 years ago by abeham

  • Status changed from reviewing to readytorelease

comment:60 Changed 5 years ago by abeham

r8911: (Hopefully) fixed a problem with ziplib reference

comment:61 Changed 4 years ago by swagner

  • Resolution set to done
  • Status changed from readytorelease to closed
  • Version changed from 3.3.7 to 3.3.8
Note: See TracTickets for help on using tickets.