Sequencing two classes of jobs on a machine with an external no-idle constraint
研究单台机器上两类作业的排序问题，A类作业最小化总流动时间，B类作业需满足外部下游机器无空闲约束，证明问题为NP难，提出数学规划方法和启发式算法。
In this paper, we deal with a special type of scheduling problem. There are two classes of jobs to be processed on a single machine. Jobs of class A are directly delivered to the customers and we want to minimise their total flow time. Jobs of class B do not contribute to the objective function but must respect a no-idle constraint (i.e. they are required to keep an external downstream machine busy). This problem arises in some real-world production environments where the downstream process must not be interrupted because of technological constraints, economic viability or because the firm is bound to keep the external process continuously active (e.g. a contract with a downstream firm imposing penalties if the supply is interrupted). We prove that the general problem is NP-Hard. We introduce two mathematical programming-based approaches and some constructive heuristics. The various approaches are compared on the basis of a large computational campaign.