is this NP complete ?

sasa.swe_at_gmail.com
Date: 03/28/05

  • Next message: Qingpei Hu: "Why use graphic approach for Bayesian inference?" 
    Date: 28 Mar 2005 10:01:47 -0800

    Hello,
    I would appreciate your advice deciding if the following problem is NP
    complete or can be solved in polynomial time.

    Given a set of m processors. There are n tasks running on these m
    processors.
    The task assignment on the processors (mapping) and the execution order
    (schedule) is known (precedence constraints on tasks mapped on
    different processors and scheduling order on each processor).
    Tasks have a certain fixed execution time and a deadline (they have to
    finish all before their deadlines).
    The start time of each task is a variable.
    Due to dependencies between tasks on different processors, there is a
    certain amount of idleness.
    During idle times, we would like to switch off the processor in order
    to save energy. A shutdown operation
    comes with a fixed time and energy penalty.
    We would like to find out when to shutdown a processor and for how long
    (actually the difficulty is to decide if or not
    to shutdown at the end of a task; if we would know after which tasks to
    shutdown, an LP formulation could determine
    the size of the shutdown).

    Is this problem NP complete or not ?
    I think that the precedence constrained knapsack might be reduced to my
    problem, but I not 100% sure since in my case the
    order of tasks is given and I have to find out only if & when to
    shutdown.

    As an ILP, I would formulate the problem like this:

    minimize xshut[i]*constant_energy_overhead +
    xidle[i]*t_idle[i]*constant_idle_power

    start_time[i]+exec_time[i] +
    xshut[i]*(t_shut[i]+constant_time_overhead) + xidle[i]*t_idle[i] =
    start_time[j]; # where j $

                    # on the same processor

    start_time[i]+exec_time[i]<=tart_time[j]; # where j is a successor of
    task i
                                              # on another processor

    start_time[i]+exec_time[i]<=deadline[i];

    xshut[i] + xidle[i]=1, binary variables: xshut[i]=1 if there is a
    shutdown after i;
                                             xidle[i]=1 if there is no
    shutdown

    t_shut[i] is the length of the shutdown time after task i
    t_idle[i] is the length of the idle time after task i

    Thanks for your suggestions.
    Best wishes,
    Alexandru

  • Next message: Qingpei Hu: "Why use graphic approach for Bayesian inference?"