最短平均等待时间问题

问题描述

• 设有n个顾客同时等待同一项服务，顾客i需要的服务时间为t_i(1<=i<=n)，应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n个顾客等待服务时间的总和除以n

代码实现

流程图

public class Waiting {

    public static void main(String[] args) {
        float[] w = {1, 3, 10, 5, 3, 5, 6, 8, 1, 2, 12};
        int n = w.length;
        float[] x = new float[n];
        int[] order = new int[n];
        float T = Waiting(x, w, n, order);
        for (int i = 0; i < n; i++) {
            System.out.printf("%3d：服务时间： %5.2f 服务顺序： %3d 等待时间： %5.2f\n", (i + 1), w[i], (order[i] + 1), x[i]);
        }
        System.out.printf("平均等待时间为： %.2f分钟", T);
    }

    public static float Waiting(float[] x, float[] w, int n, int[] order) {
        int[] t = new int[n];
        Sort(w, t, n);
        int temp = 0;
        float T = 0;
        for (int i = 0; i < n; i++) {
            x[t[i]] = temp;
            temp += w[t[i]];
            order[t[i]] = i;
        }
        for (int i = 0; i < n; i++) {
            T += x[i];
        }
        return T / n;
    }

    public static void Sort(float[] w, int[] t, int n) {
        float[] array = w.clone();
        float temp;
        int index;
        for (int i = 0; i < n; i++) {
            t[i] = i;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;

                    index = t[j];
                    t[j] = t[j + 1];
                    t[j + 1] = index;
                }
            }
        }
    }
}

• float Waiting(float[] x, float[] w, int n, int[] order)：计算最短平均等待时间。
  • float[] x：每位顾客的等待时间。
  • float[] w：每位顾客的服务时间。
  • int n：顾客的数量。
  • int[] order：顾客被服务的顺序。
  • return：最短平均等待时间。
• Sort(float[] w, int[] t, int n)：通过服务时间由小到大将顾客排序。
  • float[] w：每位顾客的服务时间。
  • int[] t：排序后w数组的下标顺序。
  • int n：顾客的数量。