Minimize Total Processing Time in a Dual-Machine Factory

A processing factory has two machines, A and B. Each product can be processed by either machine alone or by both machines working simultaneously. Due to machine performance and product characteristics, the processing times differ. For a given product:

• If processed solely on machine A, it takes time \(t_1\).
• If processed solely on machine B, it takes time \(t_2\).
• If processed jointly by both machines, it takes time \(t_3\).

A task always must be completed by one of these three processing modes. When a task is processed individually on one machine, the other machine remains idle; but when a task is processed jointly, the two machines work concurrently for \(t_3\) time and both are busy during that period.

You are given \(n\) products (tasks) with different work loads. For the \(i\)-th task, you are given the three processing times \(t_{1,i}\), \(t_{2,i}\) and \(t_{3,i}\). Your goal is to decide, for every task, its processing mode (machine A only, machine B only, or jointly by both machines) as well as an appropriate scheduling order such that the overall completion time is minimized.

The total completion time is computed as follows. Suppose you assign some tasks to be processed individually (either on machine A or B) and let \(S_A\) be the sum of processing times on machine A and \(S_B\) be the sum on machine B, where these tasks run concurrently on the two machines. Let \(J\) be the total processing time for the tasks processed jointly (since they must be processed one after the other because both machines are occupied). Then the overall finish time is

[ T = \max{S_A, S_B} + \sum_{\text{joint tasks}} t_{3},. ]

Design an algorithm to choose an assignment for each task (one of the three options) so that \(T\) is minimized.

inputFormat

The first line contains an integer \(n\) (the number of tasks). Each of the next \(n\) lines contains three positive integers \(t_1\), \(t_2\) and \(t_3\) separated by spaces, representing the processing times for that task in mode A-only, mode B-only and joint processing, respectively.

outputFormat

Output a single integer representing the minimum total completion time.

sample

1
3 5 4

3