Three-machine proportionate flow shop problem with unequal machine

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

• What is the code efficiency?

• How can I calculate it by myself?

• 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

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.

-
multipl

StackExchange Code Review Q#51198, answer score: 6