A linear time-cost tradeoff problem with multiple milestones under a comb graph

We consider a linear time-cost tradeoff problem (LTCTP) with multiple milestones under a comb graph. A time-cost tradeoff problem decides whether and how much to spend a cost to compress processing time of a job in order to meet promised due dates. This is common in managing a project because additional labors or resources are expensive. It is called linear where the compression cost linearly increases with reduced time. An objective of the LTCTP that this study addresses is to minimize the weighted number of tardy milestones plus the total compression cost. This study considers a special precedence structure, which is called a comb graph. A chain of jobs that sequentially precede each other forms a main process of a project, and other chains of jobs, corresponding to sub processes, precede each job in the main process. For this structure, we developed a strongly-polynomial-time algorithm. This is the first result of unveiling complexity of the multi-milestone LTCTP under a non-chain structure.