The projects so as to minimize the maximum tardiness

Reference no: EM131121856

A busy professor has to complete N projects. Each project i has a deadline di and the time it takes the professor to complete it is Ti. The professor can work on only one project at a time and must complete it before moving on to a new project. For a given order of completion of the projects, denote by ti the time of completion of project i, i.e

The professor wants to order the projects so as to minimize the maximum tardiness, given by

Use an interchange argument (cf. Exercise 10.24) to show that it is optimal to complete the projects in the order of their deadlines (do the project with the closest deadline first).

Reference no: EM131121856

Questions Cloud

Show that to maximize the expected reward : The Quiz Problem) Consider a quiz contest where a person is given a list of N questions and can answer these questions in any order he chooses. Question i will be answered correctly with probability pi, independently of earlier answers, and the pe..

What is the optimal product mix for problem : The objective of a linear programming problem is to maximize 1.50A + 1.50B, subject to 3A + 2B ≤ 600, 2A + 4B ≤ 600, and 1A + 3B ≤ 420. a. Plot the constraints on the grid below b. Identify the feasible region and its corner points. Show your work. c..

Monotonically nondecreasing sequences of numbers : (Hardy's Theorem) be monotonically nondecreasing sequences of numbers. Let us associate with each i = 1,...,n a distinct index ji, and consider Use an interchange argument

What is the optimal solution and max profit : A craftsman builds two kinds of birdhouses, one for wrens (X1), and one for bluebirds (X2). Each wren birdhouse takes four hours of labor and four units of lumber. Each bluebird house requires two hours of labor and twelve units of lumber. What is th..

The projects so as to minimize the maximum tardiness : A busy professor has to complete N projects. Each project i has a deadline di and the time it takes the professor to complete it is Ti. The professor can work on only one project at a time and must complete it before moving on to a new project. F..

Explain why the court upheld the virginia statute : What did the Court mean when it held, in Virginia v. Black, that "just as any State may regulate only that obscenity which is the most obscene due to its prurient content, so too may a State choose to prohibit only those forms of intimidation that..

Audience with uniquely different emotions : Deliverable length: 2 letters, 4–6 paragraphs each You are to write 2 letters/e-mails that will require 2 separate appeals, each of which is intended for an audience with uniquely different emotions. Use the components of persuasive messages that you..

Impairment roland company uses special strapping equipment : Repeat the requirements for (a) and (b), assuming that Roland intends to dispose of the equipment and that it has not been disposed of as of December 31, 2011.

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.,

User Account

All Pages