A preference-based framework for the value of information in online scheduling: the single-machine now-or-later decision

Production scheduling increasingly requires decisions to be taken in real time, without complete knowledge of the jobs still to come. Competitive analysis provides worst-case guarantees for online algorithms but does not price the individual pieces of information a scheduler might acquire. This paper develops a preference-based framework that values information by the reduction it produces in the Pareto optimal action set.

We apply it to a single, local, binary decision epoch of the single machine problem ($ 1|online, r_j|\sum C_j $): the now-or-later choice between dispatching the job in hand and idling for one announced arrival. It is a building block rather than a policy (we derive no competitive ratio), and this restriction is what makes closed-form values attainable. The optimal action depends on the two parameters only through a single comparison between the resequencing gain and the total waiting cost imposed on the queued jobs, so one bit of advice is necessary and sufficient. We obtain closed-form expected values when only one parameter is observed, together with an acquisition rule when forecasts are costly. Which forecast is worth more is governed by the upper tail of the gain distribution rather than by congestion alone: No crossover occurs for a power law of index $ \alpha < 2 $, whereas release-delay information prevails beyond a finite crossover for bounded or light-tailed gains. Evaluating the closed forms across five gain distributions places that crossover between 10 queued jobs and never.