Solution of a bilevel optimistic scheduling problem on parallel machines
研究了均匀并行机上的双层乐观调度问题，领导者分配作业给跟随者以最小化加权延迟作业数，跟随者调度作业以最小化总完工时间，提出了分支定界算法和列生成方法，实验支持最多100个作业和4台机器。
Abstract We consider the uniform parallel machines scheduling problem in the context of optimistic bilevel optimization, where two speed options are considered. In this scenario, the leader selects and assigns a subset of jobs to the follower to minimize the weighted number of tardy jobs, while the follower schedules these jobs on a set of uniform machines to minimize the total completion time. This problem has practical applications in Industry 4.0. We show that this problem is $$\mathcal NP$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>N</mml:mi> <mml:mi>P</mml:mi> </mml:mrow> </mml:math> -hard in the strong sense by providing a reduction from the Numerical 3-Dimensional Matching problem and we provide a moderately exponential-time dynamic programming algorithm. The problem is solved by means of a concise MIP formulation and a branch-and-bound algorithm that embeds a column generation approach for the lower bound computation. Computational experiments are presented for instances with up to 100 jobs and 4 machines while larger problems are out of reach for the proposed approaches.