phone Int.Acad.Publications,
Welcome to
International Conference on Economics, Engineering, Applied Computational Science (EECAS)



    Polynomially Solvable and NP-hard Special Cases for Scheduling with Heads and Tails

    Author(s): Elisa Chinos, Nodari Vakhania

    Abstract: We consider a basic single-machine scheduling problem when jobs have release and delivery times and the objective is to minimize maximum job lateness. This problem is known to be strongly NP-hard. We study inherent structure of this problem exploring its special cases and the conditions when the problem can be efficiently solved.

    Keywords: scheduling single-machine; heuristic; algorithm; release time; delivery time; due-date

    Pages: 10-14