Two-machine open shop scheduling with deteriorating job to the number of tardy jobs
CHEN Ren-xia
LI Shi-sheng
FENG Qi
MENG Jin-tao
Abstract：This paper studies the problem of scheduling proportionally deteriorating jobs in two-machine open shop to minimize the number of tardy jobs, in which all jobs have the common due date. We first show that the unweighted problem is NP-hard, then we present a pseudo-polynomial-time algorithm for the weighed problem, and finally we develop polynomial algorithms to solve several special cases.
Keywords：schedulingopen shopdeteriorating jobsNP-hardness
Publication Date：2014-11-01
Online Publishing Date：2025-08-15(First online date of this platform, not the publication date of the document)
Pages：5( 7-11 )