Adaptive model, best response b for the adversary

This file complements the paper “Scheduling with a processing time oracle” by Dufossé, Dürr, Nadal, Trystram and Vásquez.

Number of jobs: n
Short job length: p
Long job length: p + x
Numher of short tested jobs: c
Number of long tested jobs: d
Delay caused by the tests: e

Suppose algorithm decides to switch to the second phase, namely to execute all remaining n-c-d jobs untested.

Adversary chooses a number b of jobs among these which will be long.

This notebook shows how to compute the optimal value for b.

Clear[ALG,OPT,h]
ALG[b_]:=p n (n+1)/2+e+x((n-c)(n-c+1)-(n-c-b)(n-c-b+1)+d(d+1))/2;
OPT[b_]:=p n (n+1)/2+x(b+d)(b+d+1)/2;
h[b_]:=FullSimplify[ALG[b] OPT[b-1]-ALG[b-1] OPT[b]]2/x

FullSimplify[D[D[h[b],b],b]]

FullSimplify[Solve[h[b]==0,b]]

rightEnd=FullSimplify[h[n-c-d]]

alternativeForm =-2e(n-c)-p n(n+1)(n-c-d-1)-x(n-c)(n-c+1)(n-c-d-1)

FullSimplify[rightEnd-alternativeForm]

FullSimplify[h[0]]

For small p and x, h[0] could be negative. Hence b* can be negative.