Common operation scheduling with general processing times: A branch-and-cut algorithm to minimize the weighted number of tardy jobs
研究了公共操作调度问题，提出0-1线性规划模型和分支切割算法，在单机和并行机两种情形下最小化加权延迟任务数，实验表明新方法优于已有方法。
Common operation scheduling (COS) problems arise in real-world applications, such as industrial processes of material cutting or component dismantling. In COS, distinct jobs may share operations, and when an operation is done, it is done for all the jobs that share it. We here propose a 0-1 LP formulation with exponentially many inequalities to minimize the weighted number of tardy jobs. Separation of inequalities is in NP, provided that an ordinary min Lmax scheduling problem is in P. We develop a branch-and-cut algorithm for two cases: one machine with precedence relation; identical parallel machines with unit operation times. In these cases separation is the constrained maximization of a submodular set function. A previous method is modified to tackle the two cases, and compared to our algorithm. We report on tests conducted on both industrial and artificial instances. For single machine and general processing times the new method definitely outperforms the other, extending in this way the range of COS applications.