7
\$\begingroup\$

As part of an academic project I wrote a code about dynamic programming that solves the "Three-machine proportionate flow shop problem with unequal machine".

In flow shop scheduling it is usually assumed that the processing times of the operations belonging to the same job are unrelated. But when a job corresponds to producing a certain quantity of some good, then it is likely that the processing times are related to this quantity, and hence are constant except for some factor that depends on the speed of the machine. In this paper, we consider this special case of the flow shop problem, which we call the proportionate flow shop problem with unequal machine speeds. This is a special case of the flow shop problem with ordered processing times that has been studied by Smith, Panwalkar, and Dudek. Their results imply that makespan minimization is easy if the first or last machine is slowest; if the second machine is slowest, then there exists an optimum schedule that is V-shaped. We provide an algorithm that solves this problem (and the more general problem with ordered processing times) to optimality in pseudopolynomial time, and we show that this is best possible by establishing NP-hardness in the ordinary sense.

ACM Digital Library

My major problem is that the code takes a lot of time to calculate big values (bigger than 10).

  1. What is the code efficiency?
  2. How can I calculate it by myself?
  3. How can I make this code specifically efficient?
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Data;
using Microsoft.Office.Core;
using Excel = Microsoft.Office.Interop.Excel;
using System.Windows.Forms;

namespace PF_with_one_deferent_machine
{
    class Program
    {
        static void Main(string[] args)
        {
            double[] jobs=new double[0];
            double[] mashines_rates = new double[0];
            int num_of_jobs=0;
            double[][] examples;
            double[][] p;
            double[] sorted; 
            //getting input from user
            //jobs = new double[3] { 2, 4, 7 };
            //mashines_rates = new double[4] { 1, 1, 0.5, 1 };

            Console.WriteLine("0 - auto     1 - manual");
            Console.Write("Auto or manual input? ");
            Boolean manual=(Convert.ToInt32(Console.ReadLine())==1);
            if (manual)
            {
                #region Input manual
                Console.Write("How many jobs you have? ");
                num_of_jobs = Convert.ToInt32(Console.ReadLine());
                jobs = new double[num_of_jobs];
                for (int size = 1; size <= num_of_jobs; size++)
                {
                    Console.Write("The process time of job number " + size+": ");
                    jobs[size-1] = Convert.ToDouble(Console.ReadLine());
                }
                Console.WriteLine();
                Console.Write("How many machines you have? ");
                int num_of_machines = Convert.ToInt32(Console.ReadLine());
                mashines_rates = new double[num_of_machines];
                for (int size = 1; size <= num_of_machines; size++)
                {
                    Console.Write("The rate time of the machine number " + size + ": ");
                    mashines_rates[size - 1] = Convert.ToDouble(Console.ReadLine());
                }
            #endregion
                manualRun(jobs, mashines_rates);

                sorted = jobs;
                MergeSort_Recursive(sorted, 0, jobs.Length - 1); //sort array from small to big
                Array.Reverse(sorted);  //reverse array (from big to small in this case)
                p = MakeP(sorted, mashines_rates);
                DynamicProgramming(p);
                Console.ReadKey();
            }else{
                #region Auto input 
                Console.Write("How many examples do you want to run? ");
                int num_of_ex= Convert.ToInt32(Console.ReadLine());
                Console.Write("How many jobs you have? ");
                num_of_jobs = Convert.ToInt32(Console.ReadLine());
                Console.Write("What is maximum job value? ");
                int maximum = Convert.ToInt32(Console.ReadLine());
                Console.Write("How many machines you have? ");
                int num_of_machines = Convert.ToInt32(Console.ReadLine());
                mashines_rates = new double[num_of_machines];
                for (int size = 1; size <= num_of_machines; size++)
                {
                    Console.Write("The rate time of the machine number " + size + ": ");
                    mashines_rates[size - 1] = Convert.ToDouble(Console.ReadLine());
                }
                examples = new double[num_of_ex][];
                Random random = new Random();
                //int maximum = 10;
                int minimum = 1;

                for (int i = 0; i < num_of_ex; i++)
                {
                    examples[i] = new double[num_of_jobs];
                    for (int j = 0; j < num_of_jobs; j++)
                    {
                        //examples[i][j] = random.NextDouble() * (maximum - minimum) + minimum;
                        examples[i][j] = random.Next(minimum,maximum);
                    }
                }
            #endregion 
                CreateOutputFile(autoRun(examples, mashines_rates));
            }
         }

        private static void DynamicProgramming(double[][] p)
        {

            int j = p[0].Length-1;
            int num_t1_options=Convert.ToInt32(p[1][1]-p[1][j]+1);
            int num_t2_options=Convert.ToInt32(p[3][1]-p[3][j]+1);

            double[][] f=new double [num_t1_options][];
            for (int i=0; i<num_t1_options; i++)
                f[i]=new double [num_t2_options];

            double dinamicMakeSpan;
            double t1 = p[1][1];
            double t2 = p[3][1];
            //DP(<current job #>,<t1>,<t2>,<ref to matrix P>)
            for (t1 = p[1][j]; t1 <= p[1][1]; t1++)
                for (t2 = p[3][j]; t2 <= p[3][1]; t2++)
                    f[Convert.ToInt32(t1 - p[1][j])][Convert.ToInt32(t2 - p[3][j])] = DP(j, t1, t2, ref p);

            double[] minArray = new double[num_t1_options];
            for (int i = 0; i < num_t1_options; i++)
                minArray[i] = f[i].Min();
            dinamicMakeSpan = minArray.Min();

            //Print all answers
            /*
            int rowCount = num_t1_options;
            int colCount = num_t2_options;
            for (int row = 0; row < rowCount; row++)
            {
                Console.Write("MakeSpan: [");
                for (int col = 0; col < colCount - 1; col++)
                    Console.Write(String.Format("{0}, ", f[row][col]));
                Console.WriteLine(String.Format("{0}]", f[row][colCount - 1]));
            }
            */

            Console.WriteLine(String.Format("Dynamic MakeSpan: {0}", dinamicMakeSpan));
        }

        private static double DP(int j, double t1, double t2, ref double[][] p)
        {
            if (j==1) //stop condition
            {
                if (t1 == p[1][1] && t2 == p[3][1])
                    return p[1][1] + p[2][1] + p[3][1];

                return 9999999999;
            }

            int num_t1_options = Convert.ToInt32(p[1][1] - p[1][j] + 1);
            int num_t2_options = Convert.ToInt32(p[3][1] - p[3][j] + 1);
            double[][] f = new double[num_t1_options][];
            for (int i = 0; i < num_t1_options; i++)
                f[i] = new double[num_t2_options];

            for (t1=p[1][j]; t1<=p[1][1]; t1++)
                for (t2=p[3][j]; t2<=p[3][1]; t2++)
                {

                    if (t1>p[1][j] && t2>p[3][j])  //case 1
                        f[Convert.ToInt32(t1 - p[1][j])][Convert.ToInt32(t2 - p[3][j])]= Math.Min( p[1][j]+DP(j-1,t1+p[2][j]-p[1][j], t2,ref p),    p[3][j]+DP(j-1,t1, t2+p[2][j]-p[3][j],ref p));


                    double [] left; double [] right;
                    double min_job=p[1][p[0].Length-1];
                    int i,size;

                    if (t1==p[1][j] && t2>p[3][j]){  //case 2

                        size =Convert.ToInt32(p[2][j]-min_job +1);
                        left = new double[size];
                        for (double t=min_job; t<=p[2][j]; t++){
                            i = Convert.ToInt32(t-min_job);
                            left[i]=p[1][j]+p[2][j]-t+DP(j-1,t,t2,ref p);
                        }
                        f[Convert.ToInt32(t1 - p[1][j])][Convert.ToInt32(t2 - p[3][j])]= Math.Min(left.Min(), p[3][j]+DP(j-1, p[1][j], t2+p[2][j]-p[3][j], ref p));
                    }//case 2

                     if (t1>p[1][j] && t2==p[3][j]){  //case 3
                        min_job=p[3][p[0].Length-1];
                        size =Convert.ToInt32(p[2][j]-min_job +1);
                        right = new double[size];
                        for (double t=min_job; t<=p[2][j]; t++){
                            i = Convert.ToInt32(t-min_job);
                            right[i]=p[3][j]+p[2][j]-t+DP(j-1,t1,t,ref p);
                        }
                        f[Convert.ToInt32(t1 - p[1][j])][Convert.ToInt32(t2 - p[3][j])]= Math.Min(right.Min(), p[1][j]+DP(j-1, t1+p[2][j]-p[1][j], t2, ref p));
                     }//case 3

                      if (t1==p[1][j] && t2==p[3][j]){  //case 4
                        min_job=p[1][p[0].Length-1];
                        size =Convert.ToInt32(p[2][j]-min_job +1);
                        left = new double[size];
                        for (double t=min_job; t<=p[2][j]; t++){
                            i = Convert.ToInt32(t-min_job);
                            left[i]=p[1][j]+p[2][j]-t+DP(j-1,t,p[3][j],ref p);
                        }

                        min_job=p[3][p[0].Length-1];
                        size =Convert.ToInt32(p[2][j]-min_job +1);
                        right = new double[size];
                        for (double t=min_job; t<=p[2][j]; t++){
                            i = Convert.ToInt32(t-min_job);
                            right[i]=p[3][j]+p[2][j]-t+DP(j-1,p[1][j],t,ref p);
                        }

                        f[Convert.ToInt32(t1 - p[1][j])][Convert.ToInt32(t2 - p[3][j])]= Math.Min(right.Min(), left.Min());  
                      }//case 4
                }// end for for
            double[] minArray = new double[num_t1_options];
            for (int i = 0; i < num_t1_options; i++)
                minArray[i] = f[i].Min();
            double dinamicMakeSpan = minArray.Min();
            return dinamicMakeSpan;
        }//end DP

        private static double[][] MakeP(double[] jobs, double[] mashines_rates) //return matrix with indexes starts from 1 and not from 0 
        {
            double[][] p;
            p = new double[mashines_rates.Length+1][];
            for (int i = 0; i <= mashines_rates.Length; i++)
                p[i] = new double[jobs.Length+1];

            for (int i = 0; i < mashines_rates.Length; i++)
                for (int j = 0; j < jobs.Length; j++)
                    p[i+1][j+1] = jobs[j] / mashines_rates[i];
            return p;
        }

        private static void manualRun(double[] jobs, double[] mashines_rates)
        {
            int num_of_vars = Factorial(jobs.Length);
            int num_of_jobs = jobs.Length;
            double[] heuristics = jobs;
            double[] heuristics_left;
            double[] heuristics_right;
            MergeSort_Recursive(heuristics, 0, jobs.Length - 1);
            Array.Reverse(heuristics);
            heuristics_left = schedule_left(heuristics);
            heuristics_right = schedule_right(heuristics);
            double makeSpan_left = find_MakeSpan(heuristics_left, mashines_rates);
            double makeSpan_right = find_MakeSpan(heuristics_right, mashines_rates);
            double makeSpan_heuristics;
            if (makeSpan_left < makeSpan_right)
            {
                makeSpan_heuristics = makeSpan_left;
                heuristics = heuristics_left;
            }
            else
            {
                makeSpan_heuristics = makeSpan_right;
                heuristics = heuristics_right;
            }


            double[][] jobs_var = make_job_variables(jobs);

            for (int i = 0; i < num_of_vars; i++)
            {
                jobs_var[i][num_of_jobs] = find_MakeSpan(jobs_var[i], mashines_rates);
            }
            sort__array_by_makeSpan<double>(jobs_var, num_of_jobs);


            double lowerBound = calcLowerBound(jobs, mashines_rates);
            double OG = jobs_var[0][num_of_jobs] / lowerBound;
            double HO = makeSpan_heuristics / jobs_var[0][num_of_jobs];
            double HLB = makeSpan_heuristics / lowerBound;

            PrintAnswer(jobs_var);

            Console.WriteLine(String.Format("Lower Bound: {0}", lowerBound));
            Console.WriteLine(String.Format("OG: {0}", OG));
            Console.WriteLine(String.Format("HO: {0}", HO));
            Console.WriteLine(String.Format("HLB: {0}", HLB));

            /*
            Console.WriteLine(String.Format("makeSpan_heuristics: {0}", makeSpan_heuristics));
            Console.WriteLine(String.Format("jobs_var[0][num_of_jobs]: {0}", jobs_var[0][num_of_jobs]));
            Console.WriteLine(String.Format("makeSpan_left: {0}", makeSpan_left));
            Console.WriteLine(String.Format("makeSpan_right: {0}", makeSpan_right));
            */
            int colCount = heuristics.Length;
            Console.Write(String.Format("makeSpan_heuristics: {0}, flow: [", makeSpan_heuristics));
            for (int col = 0; col < colCount-1 ; col++)
                Console.Write(String.Format("{0}, ", heuristics[col]));

            Console.WriteLine(String.Format("{0}]", heuristics[colCount - 1]));


        }

        private static double [][] autoRun(double[][] examples, double[] mashines_rates)
        {
            int num_of_jobs = examples[0].Length;
            int num_of_machines = mashines_rates.Length;
            int num_of_vars = Factorial(num_of_jobs);
            double[] jobs;
            double[] heuristics;
            double[] heuristics_left;
            double[] heuristics_right;
            double makeSpan_left;
            double makeSpan_right;
            double makeSpan_heuristics;
            double makeSpan_optimum;
            double[][] jobs_var;
            double lowerBound;
            double OG;
            double HO;
            double HLB;
            double[][] answer_array = new double[examples.Length][];
            for (int i = 0; i < examples.Length; i++)
            {
                answer_array[i] = new double[6 + num_of_jobs*2];
            }


            for (int i = 0; i < examples.Length; i++)
            {
                jobs = new double[num_of_jobs];
                for (int job = 0; job < num_of_jobs; job++)
                {
                    jobs[job] = examples[i][job];
                }

                #region Make heuristic answer
                    heuristics = jobs;
                    MergeSort_Recursive(heuristics, 0, jobs.Length - 1);
                    Array.Reverse(heuristics);
                    heuristics_left = schedule_left(heuristics);
                    heuristics_right = schedule_right(heuristics);
                    makeSpan_left = find_MakeSpan(heuristics_left, mashines_rates);
                    makeSpan_right = find_MakeSpan(heuristics_right, mashines_rates);
                    if (makeSpan_left < makeSpan_right)
                    {
                        makeSpan_heuristics = makeSpan_left;
                        heuristics = heuristics_left;
                    }
                    else
                    {
                        makeSpan_heuristics = makeSpan_right;
                        heuristics = heuristics_right;
                    }
                #endregion

                #region Make optimum answer
                    jobs_var = make_job_variables(jobs);
                    for (int k = 0; k < num_of_vars; k++)
                    {
                        jobs_var[k][num_of_jobs] = find_MakeSpan(jobs_var[k], mashines_rates);
                    }
                    sort__array_by_makeSpan<double>(jobs_var, num_of_jobs);
                #endregion


                lowerBound = calcLowerBound(jobs, mashines_rates);
                makeSpan_optimum=jobs_var[0][num_of_jobs];
                OG =  makeSpan_optimum/ lowerBound;
                HO = makeSpan_heuristics / makeSpan_optimum;
                HLB = makeSpan_heuristics / lowerBound;

                answer_array[i][0] = makeSpan_optimum;
                answer_array[i][1] = makeSpan_heuristics;
                answer_array[i][2] = lowerBound;
                answer_array[i][3] = OG;
                answer_array[i][4] = HO;
                answer_array[i][5] = HLB;
                for (int p = 0; p < num_of_jobs; p++)
                {
                    answer_array[i][p + 6] = jobs_var[0][p];
                }
                for (int p = 0; p < num_of_jobs; p++)
                {
                    answer_array[i][p + 6 + num_of_jobs] = heuristics[p];
                }


                //SaveExample(heuristics, makeSpan_heuristics, jobs, lowerBound);

                /*
                if (OG < 1) //if Lower Bound is fail
                {
                    Console.WriteLine("LowerBound is fail!");
                    Console.WriteLine(String.Format("Optimum: {0}", jobs_var[0][num_of_jobs]));
                    Console.WriteLine(String.Format("lowerBound: {0}", lowerBound));

                    int colCount = jobs_var[0].Length - 1;
                    Console.Write(String.Format("MakeSpan: {0}, flow: [", jobs_var[0][colCount]));
                    for (int col = 0; col < colCount - 1; col++)
                        Console.Write(String.Format("{0}, ", jobs_var[0][col]));

                    Console.WriteLine(String.Format("{0}]", jobs_var[0][colCount - 1]));
                    Console.ReadKey();
                } */
            }
            return answer_array;
        }


        private static double[] schedule_right(double[] heuristics)
        {
            double[] scheduled = new double[heuristics.Length];
            if (heuristics.Length % 2 == 0)
            {
                int place = heuristics.Length / 2 ;
                scheduled[place] = heuristics[0];
                int counter = 1;
                int job_counter = 1;
                for (int i = 1; i < heuristics.Length; i++)
                {
                    scheduled[place - counter] = heuristics[i];
                    job_counter++;
                    if (job_counter < heuristics.Length)
                    {
                        scheduled[place + counter] = heuristics[i + 1];
                        job_counter++;
                        i++;
                    }
                    counter++;
                }
            }
            else
            {
                int counter = 1;
                int place = heuristics.Length / 2;
                scheduled[place] = heuristics[0];
                for (int i = 1; i < heuristics.Length; i++)
                {
                    scheduled[place + counter] = heuristics[i];
                    i++;
                    scheduled[place - counter] = heuristics[i];
                    counter++;
                }
            }
            return scheduled;
        }

        private static double calcLowerBound(double[] jobs, double[] mashines_rates)
        {
            double[] averages = new double[jobs.Length];
            for (int i = 0; i < jobs.Length; i++)
            {
                averages[i] = 0;
                for (int j = 0; j < mashines_rates.Length; j++)
                {
                    averages[i] += jobs[i] / mashines_rates[j];
                }
                averages[i] = averages[i] / mashines_rates.Length;
            }
            //double answer = averages.Sum() + averages.Max() * (mashines_rates.Length - 1);
            double average = averages.Sum() / averages.Length;
            double lowerBound = average * averages.Length + average * (mashines_rates.Length - 1);
            //Console.Write(String.Format("Lower Bound: {0}", lowerBound));
            return lowerBound;

        }

        private static void sort__array_by_makeSpan<T>(T[][] jobs_var, int col) 
        {
            Comparer<T> comparer = Comparer<T>.Default;
            Array.Sort<T[]>(jobs_var, (x, y) => comparer.Compare(x[col], y[col])); 
        }

        private static void PrintAnswer(double[][] jobs_var)
        {
            Console.WriteLine();
            Console.WriteLine();
            Console.WriteLine();
            int rowCount = Math.Min(40,jobs_var.Length);
            int colCount = jobs_var[0].Length-1;
            for (int row = 0; row < rowCount; row++)
            {
                Console.Write(String.Format("MakeSpan: {0}, flow: [", jobs_var[row][colCount]));
                for (int col = 0; col < colCount-1; col++)
                    Console.Write(String.Format("{0}, ", jobs_var[row][col]));

                Console.WriteLine(String.Format("{0}]", jobs_var[row][colCount-1]));
            }
        }

        private static void PrintHeuristicAnswer(double[] jobs_var)
        {
            Console.WriteLine();
            Console.WriteLine();
            Console.WriteLine();

            int colCount = jobs_var.Length - 1;
            Console.Write(String.Format("MakeSpan: {0}, flow: [", jobs_var[colCount]));
            for (int col = 0; col < colCount - 1; col++)
                Console.Write(String.Format("{0}, ", jobs_var[col]));
            Console.WriteLine(String.Format("{0}]", jobs_var[colCount - 1]));
        }

        private static double find_MakeSpan(double[] jobs_array, double[] mashines_rates)
        {
            int num_of_jobs = jobs_array.Length;
            int num_of_machines = mashines_rates.Length;
            double[] flows = new double[num_of_machines];
            double makespan;
            for (int i = 0; i < num_of_machines; i++)
            {
                flows[i] = 0;
            }
            for (int i = 0; i < num_of_jobs; i++)
            {
                flows[0] += jobs_array[i] / mashines_rates[0];
                for (int j = 1; j < num_of_machines; j++)
                {
                    flows[j] = Math.Max(flows[j - 1], flows[j]) + jobs_array[i] / mashines_rates[j];
                }
            }
            makespan = flows[num_of_machines - 1];
            return makespan;
        }

        private static int Factorial(int i)
        {
            if (i <= 1)
            return 1;
            return i * Factorial(i - 1);   
        }

        private static double[][] make_job_variables(double[] jobs)
        {
            double[][] jobs_vars;
            int num_of_vars=Factorial(jobs.Length);
            jobs_vars = new double[num_of_vars][];
            for (int i=0; i<num_of_vars; i++){
                jobs_vars[i] = new double[jobs.Length + 1];
                jobs_vars[i][jobs.Length] = 0;
            }
            int count = 0;
            foreach (double[] permutation in Permutations<double>.AllFor(jobs))
            {
                for (int i = 0; i < jobs.Length; i++)
                {
                    jobs_vars[count][i] = permutation[i];
                }
                count++;
            }
            return jobs_vars;
        }

        static public void DoMerge(double[] numbers, int left, int mid, int right)
        {
            double[] temp = new double[25];
            int i, left_end, num_elements, tmp_pos;
            left_end = (mid - 1);
            tmp_pos = left;
            num_elements = (right - left + 1);
            while ((left <= left_end) && (mid <= right))
            {
                if (numbers[left] <= numbers[mid])
                    temp[tmp_pos++] = numbers[left++];
                else
                    temp[tmp_pos++] = numbers[mid++];
            }
            while (left <= left_end)
                temp[tmp_pos++] = numbers[left++];
            while (mid <= right)
                temp[tmp_pos++] = numbers[mid++];
            for (i = 0; i < num_elements; i++)
            {
                numbers[right] = temp[right];
                right--;
            }
        }

        static public void MergeSort_Recursive(double[] numbers, int left, int right)
        {

            int mid;
            if (right > left)
            {
                mid = (right + left) / 2;
                MergeSort_Recursive(numbers, left, mid);
                MergeSort_Recursive(numbers, (mid + 1), right);
                DoMerge(numbers, left, (mid + 1), right);
            }
        }
    }

    public class Permutations<T>
    {
        public static System.Collections.Generic.IEnumerable<T[]> AllFor(T[] array)
        {
            if (array == null || array.Length == 0)
            {
                yield return new T[0];
            }
            else
            {
                for (int pick = 0; pick < array.Length; ++pick)
                {
                    T item = array[pick];
                    int i = -1;
                    T[] rest = System.Array.FindAll<T>(
                        array, delegate(T p) { return ++i != pick; }
                    );
                    foreach (T[] restPermuted in AllFor(rest))
                    {
                        i = -1;
                        yield return System.Array.ConvertAll<T, T>(
                            array,
                            delegate(T p)
                            {
                                return ++i == 0 ? item : restPermuted[i - 1];
                            }
                        );
                    }
                }
            }
        }
    }
\$\endgroup\$
  • \$\begingroup\$ Have you tried profiling your code? \$\endgroup\$ – svick May 20 '14 at 12:07
  • 1
    \$\begingroup\$ I see lots of extra writelines and writes in nested loops, while the code is also written in a non-object-oriented manner (enough so that I'm starting to wonder why you're even using C#!). Wouldn't one Console.Write("\n\n\n") be clearer than triple writelines? Maybe moreso as a method? Can't all your regions be methods? I expect many won't want to review it before at least that much is done. \$\endgroup\$ – Magus May 20 '14 at 14:28
  • \$\begingroup\$ Definitely run this through a performance profiler, the one built into VS2012 works great for .net assemblies (Analyze > Launch Performance Wizard). \$\endgroup\$ – James Aug 23 '14 at 5:39
  • \$\begingroup\$ I'm afraid this question does not match what this site is about. Code Review is about improving the cleanliness of existing and working code. Code Review is not the site to ask for help in fixing or changing what your code does. Once the code does what you want, we would love to help you to do the same thing in a cleaner way! \$\endgroup\$ – Heslacher Nov 13 '14 at 10:58
  • 1
    \$\begingroup\$ What exactly is "Three-machine proportionate flow shop problem with unequal machine"? I would like to see more description about that in your question. \$\endgroup\$ – Simon Forsberg Nov 13 '14 at 13:09
6
+300
\$\begingroup\$

Missing methods

The posted code is missing the schedule_left() and CreateOutputFile() method.

Style

  • you should always be consistent in the style you use. Switching from not using braces {} to using them for single for loops should be avoided. The same is true for single if statements.

  • dead code should be deleted

  • if you decide to not using braces for single if statements you should indent your code. See

    private static int Factorial(int i)
    {
        if (i <= 1)
        return 1;
        return i * Factorial(i - 1);   
    }
    
  • using region's is discussed controversially, but using region's inside a method is a sign that this "region" should be extracted to its own method.

Naming

Reading and understanding is all about words we use e.g to explain a question and its solution. These words needs to be meaningful to the reader as well as to the author.
Shortening these names to e.g p doesn't add readability but removes it.

Based on the naming guidelines methods should be named using PascalCase casing and should be made out of verbs or verb phrases. Fields or variable should be named using camelCase casing. snake_Case casing isn't used in C#.

General

  • you shouldn't add references you don't use. -> using Excel = Microsoft.Office.Interop.Excel;
  • you have many magic numbers in your code. You should consider to extract them into meaningful constants.

  • if you read input from the user, you need to add some sort of validation. Instead of blindly calling Convert.ToInt32(Console.ReadLine()) you should use Int32.TryParse().

  • you should extract the reading of the users input to a separate method like for Int32

    private static Int32 ReadInt32(String message, String errorMessage)
    {
        Console.WriteLine(message);
        Int32 input;
        while (!Int32.TryParse(Console.ReadLine(), out input))
        {
            Console.WriteLine(errorMessage);
        }
        return input;
    }   
    

    which you then call like

    int num_of_ex = ReadInt32("How many examples do you want to run? ", "You need to input a valid number, please try again.");  
    
  • starting a for loop by 1 for filling an array is strange.

    for (int size = 1; size <= num_of_jobs; size++)
    {
        Console.Write("The process time of job number " + size+": ");
        jobs[size-1] = Convert.ToDouble(Console.ReadLine());
    }  
    

    it would be better by renaming the iteration variable and also by calling a ReadDouble() method like

    for (int jobIndex = 0; jobIndex < num_of_jobs; jobIndex++)
    {
        jobs[jobIndex] = ReadDouble(String.Format("The process time of job number {0}: ", jobIndex + 1), "You need to input a valid number, please try again.");
    }  
    

DynamicProgramming()

  • this method is badly named because it isn't clear by this name what the method should do.

  • the code of creating the jagged array f is the same as in the DP() method, so this should be extracted to a separate method to remove code duplication.

    private static double[][] GetJaggedArray(int firstDimensionLength, int secondDimensionLength)
    {
        double[][] jaggedArray = new double[firstDimensionLength][];
        for (int i = 0; i < firstDimensionLength; i++)
        {
            jaggedArray[i] = new double[secondDimensionLength];
        }
        return jaggedArray;
    }  
    
  • the declaration of the loop variables t1 and t2 should be done in the loop itself.

  • the repeated use of p[1][j] and p[3][j] where j == p[0].Length - 1 asks for separate variables.

  • to get the upper bound of an array we can use the GetUpperBound() method.

  • if we use Math.Min() we can omit the minArray and because this is used in DP() also, we extract it to its own method

    private static double GetMinimum(double[][] array)
    {
        double minimum = double.MaxValue;
        for (int i = 0; i < array.GetUpperBound(0); i++)
        {
            minimum = Math.Min(minimum, array[i].Min());
        }
        return minimum;
    }
    
  • there is no need to call for each iteration of the inner loop Convert.ToInt32(t1 - p[1][j]) because this won't change. So better extract it to a variable which is set in the outer loop.

Implemented all above will lead to

private static void DynamicProgramming(double[][] p)
{

    int last = p[0].GetUpperBound(0);

    double pOneLast = p[1][last];
    double pThreeLast = p[3][last];

    int num_t1_options = Convert.ToInt32(p[1][1] - pOneLast + 1);
    int num_t2_options = Convert.ToInt32(p[3][1] - pThreeLast + 1);

    double[][] f = GetJaggedArray(num_t1_options, num_t2_options);

    for (double t1 = pOneLast; t1 <= p[1][1]; t1++)
    {
        int firstIndex = Convert.ToInt32(t1 - pOneLast);
        for (double t2 = pThreeLast; t2 <= p[3][1]; t2++)
        {
            f[firstIndex][Convert.ToInt32(t2 - pThreeLast)] = DP(last, t1, t2, ref p);
        }
    }

    Console.WriteLine(String.Format("Dynamic MakeSpan: {0}", GetMinimum(f)));
}

DP()

  • the ref keyword is not necessary.

  • multiple declarations in one line should be avoided

  • also there is no rule for where to place the opening bracket { most place it on the new line. If you choose one style you should be consistent.

  • because the element of f which is set is always the "same" f[Convert.ToInt32(t1 - p[1][j])][Convert.ToInt32(t2 - p[3][j])] we can extract these indices to separate variables to make the code more readable

    double pOneLast = p[1][j];
    double pThreeLast = p[3][j];
    
    int firstIndex = Convert.ToInt32(t1 - pOneLast);
    int secondIndex = Convert.ToInt32(t2 - pThreeLast);
    
  • if we now take a look at the case 1's condition if (t1 > p[1][j] && t2 > p[3][j]) which is now if (t1 > pOneLast && t2 > pThreeLast) we can change it to if (firstIndex > 0 && secondIndex > 0). This can be done for the other cases too.

    If we extract the processing of the different cases to separate methods like

    private static double ProcessBothNonZero(int j, double t1, double t2, double[][] p)
    {
        double pOneLast = p[1][j];
        double pThreeLast = p[3][j];
    
        double firstDP = DP(j - 1, t1 + p[2][j] - pOneLast, t2, ref p);
        double secondDP = DP(j - 1, t1, t2 + p[2][j] - pThreeLast, ref p);
    
        return Math.Min(pOneLast + firstDP, pThreeLast + secondDP);
    }
    
    private static double ProcessFirstIsZero(int j, double t1, double t2, double[][] p)
    {
        double pOneLast = p[1][j];
        double pTwoLast = p[2][j];
        double pThreeLast = p[3][j];
    
        double min_job = p[1][p[0].Length - 1];
        double result = double.MaxValue;
    
        for (double t = min_job; t <= pTwoLast; t++)
        {
            double firstDP = DP(j - 1, t, t2, ref p);
            result = Math.Min(result, pOneLast + pTwoLast - t + firstDP);
        }
    
        double secondDP = DP(j - 1, pOneLast, t2 + pTwoLast - pThreeLast, ref p);
    
        return Math.Min(result, pThreeLast + secondDP);
    }
    private static double ProcessSecondIsZero(int j, double t1, double t2, double[][] p)
    {
        double pOneLast = p[1][j];
        double pTwoLast = p[2][j];
        double pThreeLast = p[3][j];
        double result = double.MaxValue;
        double min_job = p[3][p[0].Length - 1];
    
        for (double t = min_job; t <= pTwoLast; t++)
        {
            double firstDP = DP(j - 1, t1, t, ref p);
            result = Math.Min(result, pThreeLast + pTwoLast - t + firstDP);
        }
        double secondDP = DP(j - 1, t1 + pTwoLast - pOneLast, t2, ref p);
        return Math.Min(result, pOneLast + secondDP);
    
    }
    private static double ProcessBothAreZero(int j, double t1, double t2, double[][] p)
    {
        double pOneLast = p[1][j];
        double pTwoLast = p[2][j];
        double pThreeLast = p[3][j];
        double min_job = p[1][p[0].Length - 1];
        double result = double.MaxValue;
    
        for (double t = min_job; t <= pTwoLast; t++)
        {
            double firstDP = DP(j - 1, t, pThreeLast, ref p);
            result = Math.Min(result, pOneLast + pTwoLast - t + firstDP);
        }
    
        min_job = p[3][p[0].Length - 1];
    
        for (double t = min_job; t <= p[2][j]; t++)
        {
            double secondDP = DP(j - 1, pOneLast, t, ref p);
            result = Math.Min(result, pThreeLast + pTwoLast - t + secondDP);
        }
    
        return result;
    }  
    

    Yes, I know they are named poorly but without having enough domain specific knowledge this can happen.

    The former DP() method will then look like

    private static double DP(int j, double t1, double t2, ref double[][] p)
    {
    
        if (j == 1)
        {
            if (t1 == p[1][1] && t2 == p[3][1])
            {
                return p[1][1] + p[2][1] + p[3][1];
            }
            return double.MaxValue;
        }
    
        double pOneLast = p[1][j];
        double pThreeLast = p[3][j];
    
        int num_t1_options = Convert.ToInt32(p[1][1] - pOneLast + 1);
        int num_t2_options = Convert.ToInt32(p[3][1] - pThreeLast + 1);
    
        double[][] f = GetJaggedArray(num_t1_options, num_t2_options);
    
        for (t1 = pOneLast; t1 <= p[1][1]; t1++)
        {
            int firstIndex = Convert.ToInt32(t1 - pOneLast);
            for (t2 = pThreeLast; t2 <= p[3][1]; t2++)
            {
                int secondIndex = Convert.ToInt32(t2 - pThreeLast);
    
                if (firstIndex > 0 && secondIndex > 0)
                {
                    f[firstIndex][secondIndex] = ProcessBothNonZero(j, t1, t2, p);
                }
    
                if (firstIndex == 0 && secondIndex > 0)
                {
                    f[firstIndex][secondIndex] = ProcessFirstIsZero(j, t1, t2, p);
                }
    
                if (firstIndex > 0 && secondIndex == 0)
                {
                    f[firstIndex][secondIndex] = ProcessSecondIsZero(j, t1, t2, p);
                }
    
                if (firstIndex == 0 && secondIndex == 0)
                {
                    f[firstIndex][secondIndex] = ProcessBothAreZero(j, t1, t2, p);
                }
            }
        }
        return GetMinimum(f);
    }  
    

MakeP()

Using the new GetJaggedArray() method, this can be simplified to

/// <summary>
/// return matrix with indexes starts from 1
/// </summary>
private static double[][] MakeP(double[] jobs, double[] mashines_rates)
{
    double[][] p = GetJaggedArray(mashines_rates.Length + 1, jobs.Length + 1);

    for (int i = 0; i < mashines_rates.Length; i++)
    {
        for (int j = 0; j < jobs.Length; j++)
        {
            p[i + 1][j + 1] = jobs[j] / mashines_rates[i];
        }
    }
    return p;
}  

calcLowerBound()

By renaming the method to CalculateLowerBound() and extracting the calculation of the average to a separate method the former calcLowerBound() method is much more readable.

private static double CalculateLowerBound(double[] jobs, double[] mashines_rates)
{
    double average = 0;
    for (int i = 0; i < jobs.Length; i++)
    {
        average += GetAverage(jobs[i], mashines_rates);
    }
    average = average / jobs.Length;
    return average * jobs.Length + average * (mashines_rates.Length - 1);
}
private static double GetAverage(double job, double[] maschineRates)
{
    double average = 0;
    for (int j = 0; j < maschineRates.Length; j++)
    {
        average += job / maschineRates[j];
    }
    return average / maschineRates.Length;
}  

find_MakeSpan()

By removing the not needed initialisation for loop and directly returning the result this can be simplified to

    private static double Find_MakeSpan(double[] jobs, double[] machineRates)
    {
        int numberOfJobs = jobs.Length;
        int numberOfMachines = machineRates.Length;
        double[] flows = new double[numberOfMachines];
        for (int i = 0; i < numberOfJobs; i++)
        {
            flows[0] += jobs[i] / machineRates[0];
            for (int j = 1; j < numberOfMachines; j++)
            {
                flows[j] = Math.Max(flows[j - 1], flows[j]) + jobs[i] / machineRates[j];
            }
        }
        return flows[numberOfMachines - 1];
    }  

make_job_variables()

By renaming the method to CreateJobVariables() and removing the not needed initialisation for loop and using the new GetJaggedArray() method, this can be simplified to

private static double[][] CreateJobVariables(double[] jobs)
{

    int num_of_vars = Factorial(jobs.Length);
    double[][] jobs_vars = GetJaggedArray(num_of_vars, jobs.Length + 1);

    int count = 0;
    foreach (double[] permutation in Permutations<double>.AllFor(jobs))
    {
        for (int i = 0; i < jobs.Length; i++)
        {
            jobs_vars[count][i] = permutation[i];
        }
        count++;
    }
    return jobs_vars;
}  
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.