Scheduling problems viewed as assignment problems

Reference no: EM131121848

(Scheduling Problems Viewed as Assignment Problems) A machine can be used to perform a subset of N given tasks over T time periods. At each time period t, only a subset A(t) of tasks can be performed. Each task j has value _j (t) when performed at period t.

(a) Formulate the problem of finding the sequence of tasks of maximal total value as an assignment problem. Hint: Assign time periods to tasks.

(b) Suppose that there are in addition some precedence constraints of the general form: Task j must be performed before task j can be performed. Formulate the problem as an assignment problem with side constraints and integer constraints. Give an example where the integer constraints are essential.

(c) Repeat part (b) for the case where there are no precedence constraints, but instead some of the tasks require more than one time period

Reference no: EM131121848

Questions Cloud

Weighted shortest processing time first rule : (Weighted Shortest Processing Time First Rule) We want to schedule N tasks, the ith of which requires Ti time units. Let ti denote the time of completion of the ith task, i.e.,

Discuss the arguments for and against the capitalization : Calculate Darby Sporting Goods Inc.'s 2011 depreciation expense, for book purposes, for each of the properties acquired from Encino Athletic Equipment Company.

Scheduling and the interchange argument : (Scheduling and the Interchange Argument) In some scheduling problems it is useful to try to characterize a globally optimal solution based on the fact that it is locally optimal with respect to the 2-OPT heuristic.

Result in the process with six- sigma capability : Natural Foods sells Takeoff, a breakfast cereal, in one-pound boxes. According to Food and Drug Administration (FDA) regulations, a one- pound box must contain at least 15.5 ounces of cereal. However, Natural Food’s box- filling process is not perfec..

Scheduling problems viewed as assignment problems : (Scheduling Problems Viewed as Assignment Problems) A machine can be used to perform a subset of N given tasks over T time periods. At each time period t, only a subset A(t) of tasks can be performed. Each task j has value j (t) when performed at ..

Develop a network security policy for environment : Give consideration to each service, and recommend protection measures. Risk mitigation is of extreme importance. Confidentiality and integrity are important factors of network security. However, it should not affect availability.

Despite social differences among individuals-culture-race : Sociologists explain that despite social differences among individuals, such as language, culture, race, ethnicity, religion, age, gender, and social class, we all have the capacity to communicate with one another. Discuss the following: What are som..

Rollout algorithms based on greedy algorithms : Rollout Algorithms Based on Greedy Algorithms) In the context of the rollout algorithm, suppose that given a partial solution

Assume that the roads are usable only for logging : Compute the amount of depreciation and depletion expense for each of the 3 years (2010, 2011, 2012). Assume that the roads are usable only for logging and therefore are included in the depletion base.

User Account

All Pages