Variants and objectives for ordinal scheduling

Abstract In ordinal scheduling problems, jobs are presented sorted by non-increasing sizes. However, it is not known in advance how many jobs of positive sizes will be presented, and what their exact sizes will be. This information is revealed only when the algorithm terminates. We analyze several variants for this problem with different objectives. The main studied model is where the number of machines $$m\ge 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> is also not known in advance, and only an upper bound $$M\ge m$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>M</mml:mi> <mml:mo>≥</mml:mo> <mml:mi>m</mml:mi> </mml:mrow> </mml:math> is given. Jobs have to be partitioned into M inseparable groups called bags, which will be combined by the algorithm afterwards. The bags are to be merged one by one, where merging is applied until the actual number of machines m is reached, and the output consists of the m bags. We analyze this model with respect to maximization of the minimum load. We also discuss a variant where the merging process is based on the knowledge of m but not on job sizes, and we study additional objectives including makespan minimization.