Scheduling Four Chains on Three Parallel Machines
Abstract：A problem of scheduling n tasks with four chain-precedence constraints on three parallel machines is considered.The objective is minimize the makespan.This paper explain the NP-hardness of this problem,which computational complexity is characterized by giving a pseudo-polynomial time algorithm and a FPTAS.
Keywords：schedulingchain-precedence constraintsdynamic programcomputational complexityFPTAS
Publication Date：2011-01-01
Online Publishing Date：2026-08-28(First online date of this platform, not the publication date of the document)
Pages：5( 37-40,51 )