1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
makkiz [27]
3 years ago
12

Barr the Bear has started a business to sell fish to Poe and his fellow penguins. The penguin customers submit many fish orders,

but Barr can only process one order at a time. Suppose that Barr currently has orders from n penguin customers (label them as 1, 2, . . . , n). Customer i’s order takes ti time to complete. Barr is going to process each penguin’s order one by one, and the scheduling of orders can be described as a permutation of the customers. Let Ci denote the completion time of order i. For instance, if customer j’s order is the first to be completed, then we would have Cj = tj (assume Barr begins processing orders at time 0); if customer k’s order is the second to be completed after that, then Ck = Cj + tk = tj + tk, and so on. Each customer is of different importance to Barr’s business, and we denote this relative weight by wi (for customer i). Barr wishes to minimize the weighted sum of the completion times of n orders, Pn i=1 wi · Ci . Intuitively, the more important a customer is, the sooner Barr wishes to complete the customer’s order. Design an O(n log n) algorithm to solve this problem to help Barr. You are given a set of n orders with a processing time ti and a weight wi for each customer i (assume ti , wi are positive integers). You want to decide an ordering of the customer orders so as to minimize the weighted sum of the completion times. Prove correctness of your algorithm (i.e., optimality) and analyze its runtime.
Computers and Technology
1 answer:
luda_lava [24]3 years ago
5 0

Answer:

Algorithm below designed using Java

Explanation:

import java.util.SortedMap;

import java.util.TreeMap;

import java.util.Vector;

public class SchedulingProblem {

static Vector<Integer> processTime = new Vector<>();

static Vector<Integer> processWeight = new Vector<>();

static SortedMap<Integer, Double> timeWeightRatio = new TreeMap<Integer, Double>() {

};

 

static int number = 2;

public static void main(String[] args) {

processTime.add(1);

processWeight.add(10);

processTime.add(3);

processWeight.add(2);

for (int i = 0; i < number; i++) { // O(N)

timeWeightRatio.put(i, processWeight.get(i) / (processTime.get(i) * 1.0)); // O(log(n))

}

// ------------ O(nlog(n))

int sum = 0, tmpTime = 0;

while (timeWeightRatio.size() > 0) { // O(n)

tmpTime += processTime.get(timeWeightRatio.firstKey()); // O(n)

sum += processWeight.get(timeWeightRatio.firstKey()) * tmpTime; // O(n)

System.out.print(processWeight.get(timeWeightRatio.firstKey()) + " * " + tmpTime + ((timeWeightRatio.size() > 1) ? " + " : " = " + sum));

timeWeightRatio.remove(timeWeightRatio.firstKey()); // O(log(n))

}

 

// >>>> O(nlog(n))

}

}

You might be interested in
Quick!!!!!
Vlad [161]

Answer:

B. the current affairs page

Explanation:

it's a simple question

8 0
3 years ago
Read 2 more answers
Would anyone know this
Darina [25.2K]
Time in transit would be correct
5 0
2 years ago
Read 2 more answers
Write a function named shareALetter that takes one parameter, wordList – a list of words. Create and return a dictionary in whic
Arte-miy333 [17]
Can u send anything to understand it
7 0
2 years ago
You are installing several servers that will be used as web servers to reach customers over the Internet. Where should you place
just olya [345]

Answer: DMZ

Explanation:

 DMZ is the demilitarized zone network and it is use in providing he various services to the users or customers by using the public internet. It basically contain organizational services in the logical and physical sub-network and usually works in large network.

The main purpose of DMZ that it is use as web server over the internet for reaching to the users and customers. It also add one additional layer in the organization for security purpose.

Some of the services that DMZ provides as web server, DNS and proxy server.  

4 0
3 years ago
When data can flow across a cable in both directions, this is known as___Communicating?
Ede4ka [16]

Answer:

full duplex communication.

Explanation:

In a duplex type of topology or communication, data or information can be transferred in both directions.

There are two different types of these communications

3 0
2 years ago
Other questions:
  • What are some good editing software apps for pc?
    11·1 answer
  • 10.
    13·1 answer
  • Describe three main types of testing and the order in which they are performed.
    9·2 answers
  • A personal career profile for can be used to match what you know about yourself to what you know about different careers
    7·2 answers
  • 1. You have recently been hired by a leading firm, which provides information management solutions to large corporations. As a n
    12·2 answers
  • True or false: within a database, fields can be added, deleted and edited but never moved.
    11·1 answer
  • Pressing the e key while in edit mode will exit the interaction mode<br><br> true<br><br> false
    7·1 answer
  • 1. The global economy involves trading between people from different _____
    8·1 answer
  • Which company provides a crowdsourcing platform for corporate research and development?
    9·1 answer
  • _____ oversee the work of various types of computer professionals and must be able to communicate with people in technical and n
    5·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!