schedule.cs
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Drawing2D;
using System.Windows.Forms;
namespace Scheduling
{
public class Schedule
{
private int[] jobSchedule;
private int[] macSchedule;
int j, p, m;
float[,] startTimes, finishTimes;
float[] idleTimes;
float totalIdleTime;
bool makeSpanCalculated, idleCalculated;
float makeSpan;
public Schedule(int[] js, int[] ms, int j, int p, int m)
{
this.j = j;
this.p = p;
this.m = m;
jobSchedule = js;
macSchedule = ms;
makeSpanCalculated = false;
idleCalculated = false;
makeSpan = 0;
startTimes = new float[j, p];
finishTimes = new float[j, p];
idleTimes = new float[m];
}
#region Makespan
public float MakeSpan()
{
if (makeSpanCalculated)
return makeSpan;
int[] compProcs = new int[j];
float[] totalTime = new float[m];
int?[] lastJob = new int?[m];
int?[] lastProc = new int?[m];
for (int i = 0; i < jobSchedule.Length; i++)
{
int job = jobSchedule[i];
int proc = compProcs[job];
int a = job * p + proc;
int mac = macSchedule[a];
int oldProc = compProcs[job] > 0 ? compProcs[job] - 1 : -1;
startTimes[job, proc] = Math.Max(totalTime[mac],
oldProc == -1 ? 0 : finishTimes[job, oldProc]);
//Idle time calculator
idleTimes[mac] += startTimes[job, proc] - totalTime[mac];
//
//last process and job at the machine
lastJob[mac] = job;
lastProc[mac] = proc;
//
finishTimes[job, proc] = startTimes[job, proc] + Data.DataTable[job, proc, mac];
totalTime[mac] = finishTimes[job, proc];
compProcs[job]++;
}
float result = -1;
for (int i = 0; i < j; i++)
{
result = Math.Max(finishTimes[i, p - 1], result);
}
makeSpan = result;
//find last idle times
for (int i = 0; i < m; i++)
{
if (lastProc[i] != null)
idleTimes[i] += makeSpan - finishTimes[(int)lastJob[i], (int)lastProc[i]];
else
idleTimes[i] = makeSpan;
if (i == m - 1)
idleTimes[i] = float.Parse(idleTimes[i].ToString("0.00"));
}
makeSpanCalculated = true;
return makeSpan;
}
#endregion
#region Drawing
public void DrawSchedule(Graphics grp, Control panel)
{
if (!makeSpanCalculated)
MakeSpan();
grp.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.HighQuality;
int mac = m;
int proc = p;
int job = j;
int horSpace = 40;
int vertSpace = 60;
int delWidth = 0;
#region Draw job delegate signs
for (int i = 0; i < job; i++)
{
Rectangle rect = new Rectangle(50 * i + horSpace, 15, 15, 15);
string text = "J" + (i + 1);
Point tp = new Point(rect.Right + 3, rect.Y);
using (Font font = new Font("Arial", 10))
using (SolidBrush brush = new SolidBrush(Colors.JobColors[i]))
{
grp.FillEllipse(brush, rect);
grp.DrawString(text, font, Brushes.Gray, tp);
}
if (i == job - 1)
delWidth = tp.X + 20;
}
#endregion
panel.Height = (mac * 25 + vertSpace) + 15;
panel.Width = (int)Math.Max(delWidth, makeSpan + horSpace + 15) + 35;
grp.DrawRectangle(Pens.Black, 2, 2, panel.Width - 4, panel.Height - 8);
#region Draw measure lines and texts
int idWidth = 0;
int num = (int)((makeSpan + 5) / 25);
for (int i = 0; i <= num; i++)
{
Point p1 = new Point(25 * i + horSpace, vertSpace - 3);
Point p2 = new Point(25 * i + horSpace, vertSpace + (int)((mac - 0.5) * 25) + 5);
using (Font font = new Font("Arial", 7))
{
grp.DrawLine(Pens.DarkGray, p1, p2);
string text = (25 * i).ToString();
Size size = TextRenderer.MeasureText(text, font);
Point tp = new Point(p1.X - size.Width / 2 + 2, p1.Y - size.Height);
grp.DrawString(text, font, Brushes.DarkGray, tp);
}
}
#endregion
#region Draw gray background rectangles
PointF itPo = Point.Empty;
RectangleF[] backRects = new RectangleF[mac];
for (int i = 0; i < mac; i++)
{
backRects[i] = new RectangleF(horSpace, vertSpace + 25 * i, makeSpan + 5, 15);
grp.FillRectangle(Brushes.LightGray, backRects[i]);
using (Font font = new Font("Arial", 8, FontStyle.Bold))
{
if (i == 0)
{
Size idSize = TextRenderer.MeasureText("Idle", font);
itPo = new PointF(backRects[i].X + backRects[i].Width + 10, vertSpace - 3 - idSize.Height);
grp.DrawString("Idle", font, Brushes.DarkSlateGray, itPo);
idWidth = TextRenderer.MeasureText("Idle", font).Width;
}
string idle = idleTimes[i].ToString("0.00");
Size size = TextRenderer.MeasureText(idle, font);
grp.DrawString(idle, font, Brushes.DarkGray, itPo.X + idWidth / 2 - size.Width / 2,
backRects[i].Y + backRects[i].Height / 2 - size.Height / 2 + 2);
}
}
#endregion
#region Draw machine texts
for (int i = 0; i < mac; i++)
{
using (Font font = new Font("Arial", 10))
{
string text = "M" + (i + 1);
Size size = TextRenderer.MeasureText(text, font);
PointF tp = new PointF(backRects[i].X - size.Width, backRects[i].Y);
grp.DrawString(text, font, Brushes.Gray, tp);
}
}
#endregion
#region Draw process bars and texts
for (int i = 0; i < job; i++)
{
for (int b = 0; b < proc; b++)
{
int tempJob = i;
int tempProc = b;
int o = i * p + b;
int tempMac = macSchedule[o];
float x = startTimes[i, b] + horSpace;
float y = backRects[tempMac].Y;
float height = 15;
float time = Data.DataTable[i, b, tempMac];
PointF ps1 = new PointF(x, y + 15);
PointF ps2 = new PointF(x, ps1.Y - height);
PointF ps3 = new PointF(ps2.X + time, ps2.Y);
PointF ps4 = new PointF(ps3.X, ps3.Y + height);
GraphicsPath path = new GraphicsPath();
path.AddLine(ps1, ps2);
path.AddLine(ps2, ps3);
path.AddLine(ps3, ps4);
path.CloseAllFigures();
RectangleF bar = new RectangleF(x, y, ps3.X - ps1.X, height);
using (SolidBrush brush = new SolidBrush(Colors.JobColors[i]))
{
grp.DrawPath(Pens.Black, path);
grp.FillPath(brush, path);
}
using (Font font = new Font("Arial", 7.5f))
{
string text = (i + 1) + "-" + (b + 1);
SizeF size = TextRenderer.MeasureText(text, font);
if (size.Width > bar.Width)
{
text = (b + 1).ToString();
size = TextRenderer.MeasureText(text, font);
}
PointF tp = new PointF(bar.X + bar.Width / 2 - size.Width / 2 + 3, bar.Y + height / 2 - size.Height / 2 + 1);
grp.DrawString(text, font, Brushes.Black, tp);
}
}
}
#endregion
}
#endregion
#region Repair
Random rnd = new Random();
public void Repair()
{
int num = p;
int[] used = new int[j];
List<int> pos = new List<int>();
List<int> jobs = new List<int>();
for (int i = 0; i < p * j; i++)
{
used[jobSchedule[i]]++;
if (used[jobSchedule[i]] > num)
pos.Add(i);
}
for (int i = 0; i < used.Length; i++)
{
if (used[i] < num)
{
for (int t = 0; t < num - used[i]; t++)
{
jobs.Add(i);
}
}
}
for (int i = 0; i < pos.Count; i++)
{
int t = rnd.Next(0, jobs.Count);
jobSchedule[pos[i]] = jobs[t];
jobs.RemoveAt(t);
}
}
#endregion
#region Properties
public float FitValue
{
get
{
return MakeSpan();
}
}
public int[] MacSchedule
{
get { return macSchedule; }
set { macSchedule = value; }
}
public int[] JobSchedule
{
get { return jobSchedule; }
set { jobSchedule = value; }
}
public float TotalIdleTime
{
get
{
MakeSpan();
if (idleCalculated)
return totalIdleTime;
float total = 0;
for (int i = 0; i < m; i++)
{
total += idleTimes[i];
}
totalIdleTime = total;
idleCalculated = true;
return totalIdleTime;
}
}
#endregion
#region ToString
public string JobsToString()
{
string text = "";
for (int i = 0; i < j * p; i++)
{
text += (jobSchedule[i]+1) + "";
}
return text;
}
public string MacToString()
{
string text = "";
for (int i = 0; i < j * p; i++)
{
text += (macSchedule[i] + 1) + "";
}
return text;
}
#endregion
}
}
genetic.cs
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;
namespace Scheduling
{
class GeneticMachine
{
int jobnum, procnum, macnum, krlength = 0;
bool refresh;
Schedule[] population;
Random rnd = new Random();
private Schedule best;
double progress = 0;
int produced = 0;
bool stopped;
int mutOdd;
int groupSize;
int minTimeOdd;
int popSize;
AsyncOperation aop = AsyncOperationManager.CreateOperation(null);
COTypes crossOver;
MutationTypes mutationTypes;
SelectionTypes selectionType;
public event EventHandler BestValueChanged;
public event EventHandler ProgressChanged;
int nothingFound;
public GeneticMachine(int jobs, int procs, int macs, int popsize)
{
this.jobnum = jobs;
this.procnum = procs;
this.macnum = macs;
krlength = jobs * procs;
mutOdd = 1;
minTimeOdd = 0;
groupSize = 5;
population = new Schedule[popsize];
popSize = popsize;
crossOver = COTypes.Uniform;
mutationTypes = MutationTypes.ExchangeValues;
selectionType = SelectionTypes.Tournament;
best = null;
nothingFound = 0;
}
#region Initial Pop
void CreateInitialPopulation()
{
for (int i = 0; i < population.Length; i++)
{
Schedule ciz = createNewSchedule();
population[i] = ciz;
produced++;
Progress = double.Parse((produced * 100d / 10000000).ToString("0.00"));
if (stopped)
break;
}
}
#endregion
#region Start
public void Start()
{
CreateInitialPopulation();
Procedure();
}
#endregion
void Procedure()
{
Task t1 = new Task(() =>
{
stopped = false;
while (produced < 10000000)
{
int[] nums = doSelection();
Schedule mother = population[nums[0]];
Schedule father = population[nums[1]];
Schedule child1 = doCrossover(mother, father);
Schedule child2 = doCrossover(father, mother);
doMutation(child1);
doMutation(child2);
population[nums[nums.Length - 1]] = child1;
population[nums[nums.Length - 2]] = child2;
checkBestValueChanged(child1);
checkBestValueChanged(child2);
produced++;
nothingFound++;
if (nothingFound > 300000 && refresh)
{
addNewChromosomes(popSize / 10);
nothingFound = 0;
}
Progress = double.Parse((produced * 100d / 10000000).ToString("0.00"));
if (stopped)
break;
}
});
t1.Start();
}
void addNewChromosomes(int n)
{
int[] nums = new int[n];
for (int i = 0; i < nums.Length; i++)
{
nums[i] = rnd.Next(0, population.Length);
Schedule created = createNewSchedule();
population[nums[nums.Length - 1 - i]] = created;
checkBestValueChanged(created);
produced++;
}
}
Schedule createNewSchedule()
{
int[] jobSchedule = new int[krlength];
int[] macSchedule = new int[krlength];
int[] used = new int[jobnum];
bool[] assigned = new bool[krlength];
List<int> rem = Enumerable.Range(0, jobnum).ToList();
for (int j = 0; j < krlength; j++)
{
int selJob = rem[rnd.Next(0, rem.Count)];
jobSchedule[j] = selJob;
if (rnd.Next(1, 101) <= minTimeOdd) // Optimize population by taking the smallest time
{
int minmac = Data.GetMinTimeMacForJP(selJob, used[selJob]);
int pos = selJob * procnum + used[selJob];
macSchedule[pos] = minmac;
assigned[pos] = true;
}
else
{
if (!assigned[j])
macSchedule[j] = rnd.Next(0, macnum);
}
used[selJob]++;
if (used[selJob] == procnum)
rem.Remove(selJob);
}
return new Schedule(jobSchedule, macSchedule, jobnum, procnum, macnum);
}
//***************************************************//
#region DoSelection
int[] doSelection()
{
int[] nums = null;
switch (selectionType)
{
case SelectionTypes.Tournament:
nums = tourSelection(groupSize);
break;
case SelectionTypes.RouletteWheel:
nums = rouletWheelSelection(groupSize);
break;
}
return nums;
}
#endregion
#region DoMutation
public void doMutation(Schedule child)
{
MutationTypes temp = mutationTypes;
if(rnd.Next(1, 101) <= mutOdd)
switch (temp)
{
case MutationTypes.ExchangeValues:
ExchangeValuesMutation(child);
break;
case MutationTypes.ChangeValue:
ChangeValueMutation(child);
break;
case MutationTypes.SlipBlock:
SlipBlockMutation(child);
break;
case Scheduling.MutationTypes.Replacement:
ReplacementMutation(child);
break;
}
}
#endregion
#region DoCrossover
Schedule doCrossover(Schedule mother, Schedule father)
{
COTypes temp = crossOver;
Schedule child = null;
switch (temp)
{
case COTypes.SinglePoint:
child = SinglePointCO(mother, father);
break;
case COTypes.TwoPoint:
child = TwoPointCO(mother, father);
break;
case COTypes.Uniform:
child = UniformCO(mother, father);
child.Repair();
break;
case COTypes.OrderedX:
child = OrderedCO(mother, father);
break;
}
return child;
}
#endregion
//***************************************************//
#region Stop
public void Stop()
{
stopped = true;
}
#endregion
//***************************************************//
#region Event Firings
void checkBestValueChanged(Schedule tour)
{
if (best == null || best.FitValue > tour.FitValue)
{
best = tour;
aop.Post(new System.Threading.SendOrPostCallback(delegate
{
if (BestValueChanged != null)
BestValueChanged(this, EventArgs.Empty);
}), null);
nothingFound = 0;
}
}
void fireProgressEvent()
{
aop.Post(new System.Threading.SendOrPostCallback(delegate
{
if (ProgressChanged != null)
ProgressChanged(this, EventArgs.Empty);
}), null);
}
#endregion
//***************************************************//
#region --------Selection Methods---------
#region Tour Selection
int[] tourSelection(int groupSize)
{
int[] nums = new int[groupSize];
for (int i = 0; i < nums.Length; i++)
{
nums[i] = rnd.Next(population.Length - 1);
}
sortArray(nums);
return nums;
}
void sortArray(int[] nums)
{
bool sorted = true;
while (sorted)
{
sorted = false;
for (int i = 0; i < nums.Length - 1; i++)
{
if (population[nums[i]].FitValue > population[nums[i + 1]].FitValue)
{
int temp = nums[i];
nums[i] = nums[i + 1];
nums[i + 1] = temp;
sorted = true;
}
}
}
}
#endregion
#region Roulette Wheel Selection
int[] rouletWheelSelection(int groupSize)
{
int[] nums = new int[groupSize];
for (int i = 0; i < nums.Length; i++)
{
nums[i] = rnd.Next(population.Length - 1);
}
sortArray(nums);
double[] reciprocal = new double[groupSize];
for (int i = 0; i < reciprocal.Length; i++)
{
reciprocal[i] = 1 / population[nums[i]].FitValue;
}
for (int j = 0; j < 2; j++)
{
double value = rnd.NextDouble();
for (int i = 0; i < reciprocal.Length; i++)
{
value -= reciprocal[i];
if (value <= 0)
{
nums[j] = i;
break;
}
}
}
return nums;
}
#endregion
#endregion
//***************************************************//
#region --------Crossing Overs--------
#region Uniform CO
Schedule UniformCO(Schedule mother, Schedule father)
{
int N = krlength;
int[] macs = mother.MacSchedule.Clone() as int[];
int[] jobs = mother.JobSchedule.Clone() as int[];
for (int i = 0; i < N; i++)
{
if (rnd.Next(0, 2) == 0)
{
macs[i] = father.MacSchedule[i];
}
if (rnd.Next(0, 2) == 0)
{
jobs[i] = father.JobSchedule[i];
}
}
return new Schedule(jobs, macs, jobnum, procnum, macnum);
}
#endregion
#region Two Point CO
public Schedule TwoPointCO(Schedule mother, Schedule father)
{
int N = krlength;
int elNum = rnd.Next(N / 4, 3 * N / 4);
int x = rnd.Next(0, N - 1);
int y = x + elNum - 1;
int tt = rnd.Next(0, N - 1);
int[] gens = new int[N];
for (int i = 0; i < N; i++)
gens[i] = -1;
int[] used = new int[jobnum];
for (int i = x; i <= y; i++)
{
gens[i % N] = father.JobSchedule[tt % N];
used[gens[i % N]]++;
tt++;
}
int k = 0;
for (int i = 0; i < N; i++)
{
if (gens[i] != -1) continue;
while (used[mother.JobSchedule[k]] >= procnum)
k++;
gens[i] = mother.JobSchedule[k];
used[gens[i]]++;
}
int[] macAS = mother.MacSchedule.Clone() as int[];
elNum = rnd.Next(N / 4, 2 * N / 4);
x = rnd.Next(0, N);
tt = rnd.Next(0, N);
int bound = x + elNum;
while (x < bound)
{
macAS[x % N] = father.MacSchedule[tt % N];
tt++;
x++;
}
return new Schedule(gens, macAS, jobnum, procnum, macnum);
}
#endregion
#region Single Point
public Schedule SinglePointCO(Schedule mother, Schedule father)
{
int N = krlength;
int x = rnd.Next(N / 4, 3 * N / 4);
int[] gens = new int[N];
for (int i = 0; i < N; i++)
gens[i] = -1;
int[] used = new int[jobnum];
for (int i = 0; i < x; i++)
{
gens[i] = mother.JobSchedule[i];
used[gens[i]]++;
}
int k = 0;
for (int i = x; i < N; i++)
{
if (gens[i] != -1) continue;
while (used[father.JobSchedule[k]] >= procnum)
k++;
gens[i] = father.JobSchedule[k];
used[gens[i]]++;
}
int[] macAS = new int[N];
x = rnd.Next(N / 4, 3 * N / 4);
for (int i = 0; i < x; i++)
{
macAS[i] = mother.MacSchedule[i];
}
for (int i = x; i < N; i++)
{
macAS[i] = father.MacSchedule[i];
}
return new Schedule(gens, macAS, jobnum, procnum, macnum);
}
#endregion
#region Ordered CO
Schedule OrderedCO(Schedule mother, Schedule father)
{
int N = krlength;
//Job sequence CO
int[] jobOS = new int[N];
List<int> posOS = Enumerable.Range(0, N).ToList();
List<int> fatRem = new List<int>();
int el = rnd.Next(N / 4, 2 * N / 4);
int x = rnd.Next(0, N - el);
int y = (x + el - 1);
for (int i = y + 1; i < N; i++)
{
fatRem.Add(father.JobSchedule[i]);
}
for (int i = 0; i <= y; i++)
{
fatRem.Add(father.JobSchedule[i]);
}
for (int i = x; i <= y; i++)
{
fatRem.Remove(mother.JobSchedule[i]);
}
int a = 0;
for (int i = 0; i < N; i++)
{
if (i < x || i > y)
{
jobOS[i] = fatRem[a];
a++;
}
else
{
jobOS[i] = mother.JobSchedule[i];
}
}
int[] macAS = new int[N];
for (int j = 0; j < procnum; j++)
{
x = rnd.Next(N / 3, 2 * N / 3);
for (int i = 0; i < x; i++)
{
macAS[i] = mother.MacSchedule[i];
}
for (int i = x; i < N; i++)
{
macAS[i] = father.MacSchedule[i];
}
}
return new Schedule(jobOS, macAS, jobnum, procnum, macnum);
}
#endregion
#endregion
//***************************************************//
#region --------Mutation Methods---------
#region Change Value Mutation
void ChangeValueMutation(Schedule sch)
{
int N = krlength;
int x1 = rnd.Next(0, N);
int mac = rnd.Next(0, macnum);
sch.MacSchedule[x1] = mac;
}
#endregion
#region Exchange Values Mutation
void ExchangeValuesMutation(Schedule sch)
{
int N = krlength;
int x1 = rnd.Next(0, N);
int x2 = rnd.Next(0, N);
int temp = sch.JobSchedule[x1];
sch.JobSchedule[x1] = sch.JobSchedule[x2];
sch.JobSchedule[x2] = temp;
x1 = rnd.Next(0, krlength);
x2 = rnd.Next(0, krlength);
int macTemp = sch.MacSchedule[x1];
sch.MacSchedule[x1] = sch.MacSchedule[x2];
sch.MacSchedule[x2] = macTemp;
}
#endregion
#region Slip Block Mutation
void SlipBlockMutation(Schedule sch)
{
//Job part
int N = krlength;
int el = rnd.Next(1, N);
int x1 = rnd.Next(0, N - el);
int x2 = rnd.Next(0, N - el);
x1 = Math.Min(x1, x2);
x2 = Math.Max(x1, x2);
int[] temps = new int[el];
int kk = x1;
for (int i = 0; i < temps.Length; i++)
{
temps[i] = sch.JobSchedule[kk];
kk++;
}
int step = x2 - x1;
int[] temps2 = new int[step];
for (int i = x1 + el; i < x1 + el + step; i++)
{
temps2[i - x1 - el] = sch.JobSchedule[i];
}
for (int i = x1; i < x1 + temps2.Length; i++)
{
sch.JobSchedule[i] = temps2[i - x1];
}
for (int i = x2; i < x2 + temps.Length; i++)
{
sch.JobSchedule[i] = temps[i - x2];
}
//Machine part
el = rnd.Next(1, N);
x1 = rnd.Next(0, N - el);
x2 = rnd.Next(0, N - el);
x1 = Math.Min(x1, x2);
x2 = Math.Max(x1, x2);
int[] tempMacs = new int[el];
kk = x1;
for (int i = 0; i < tempMacs.Length; i++)
{
tempMacs[i] = sch.MacSchedule[kk];
kk++;
}
step = x2 - x1;
int[] tempMacs2 = new int[step];
for (int i = x1 + el; i < x1 + el + step; i++)
{
tempMacs2[i - x1 - el] = sch.MacSchedule[i];
}
for (int i = x1; i < x1 + tempMacs2.Length; i++)
{
sch.MacSchedule[i] = te
Please explain me this c#.net code...
Under discussion
Comments (1)
- Popular
- New
- Old
You must be signed in to leave a comment
Guadalupe Gagnon
13 February 2019, 14:42
You are on the wrong site.
+1