Minimizing Average Waiting Time in an Unrelated Machine Scheduling Problem

At time 0, N car owners bring their vehicles to an automotive repair center. The center has M technicians. Each technician takes a different amount of time to repair different cars. For technician i and car j, the repair time is \(t_{ij}\).

Your task is to schedule the repair jobs by assigning each car to exactly one technician and deciding the order of repairs for each technician. The objective is to minimize the average waiting time of customers. The waiting time of a customer is defined as the period from when the car is delivered (time 0) until its repair is completed.

Note that once the jobs are assigned to a technician, the optimal ordering on that technician is to process the cars in ascending order of their repair times (i.e., the Shortest Processing Time order).

The repair time matrix is given in the input where for each car, the repair times for the M technicians are provided.

The problem can be formally described as follows:

Given an \(N \times M\) matrix \(T = [t_{ij}]\), assign each car \(j\) to a technician \(i\) and choose an order for the jobs on each technician so that the average waiting time \[ \text{Average Waiting Time} = \frac{1}{N}\sum_{\text{all jobs}} C_j \] is minimized, where \(C_j\) is the completion time of job \(j\). If a technician processes jobs in an order \(p_1, p_2, \dots, p_k\) with repair times sorted in ascending order, then the total waiting time on that technician is: \[ \sum_{i=1}^{k} \left(\sum_{j=1}^{i} t_{p_j}\right) = \sum_{i=1}^{k} (k-i+1) \cdot t_{p_i}. \]

It is known that scheduling on unrelated machines to minimize total completion time is NP-hard. For this problem, you are required to implement a heuristic that assigns each car to a technician and then orders the jobs using the SPT rule. One reasonable heuristic is to process the cars in increasing order of their minimum available repair time and assign each car to the technician that minimizes the marginal increase in waiting time.

inputFormat

The first line of input contains two integers \(N\) and \(M\) where \(N\) (\(1 \le N \le 10^3\)) is the number of cars and \(M\) (\(1 \le M \le 10^2\)) is the number of technicians.

Then follow \(N\) lines. Each line contains \(M\) positive integers. The \(j\)-th integer on the \(i\)-th line represents \(t_{ij}\), the time required by technician \(j\) to repair car \(i\) (\(1 \le t_{ij} \le 10^4\)).

outputFormat

Output a single floating point number representing the minimum possible average waiting time achieved by your schedule. The answer should be printed with two decimal places.

sample

3 2
1 2
3 1
2 3

1.67