Minimizing the number of tardy jobs in two-machine settings with common due date

作者：Della Croce Federico^*; Koulamas Christos; T'kindt Vincent

来源：Journal of Combinatorial Optimization, 2017, 34(1): 133-140.

DOI：10.1007/s10878-016-0054-4

• Scheduling
• Approximation algorithms
• Exact exponential approaches

We consider two-machine scheduling problems with job selection. We analyze first the two-machine open shop problem and provide a best possible linear time algorithm. Then, a best possible linear time algorithm is derived for the job selection problem on two unrelated parallel machines. We also show that an exact approach can be derived for both problems with complexity , p being a polynomial function of n.

• 出版日期2017-7