(Scheduling and the Interchange Argument) In some scheduling problems it is useful to try to characterize a globally optimal solution based on the fact that it is locally optimal with respect to the 2-OPT heuristic. This is known as the interchange argument, and amounts to starting with an optimal schedule and checking to see what happens when any two tasks in the schedule are interchanged. As an example, suppose that we have N jobs to process in sequential order with the ith job requiring a given time Ti for its execution. If job i is completed at time t, the reward is αt Ri, where α is a given discount factor with 0
