Program for manage the tasks of a robot, C/C++ Programming

Consider a group of n robots, numbered R2D1 through R2Dn, and m tasks, numbered 1 through m. Tasks can be different and robots are specialized, hence a given robot can only perform certain tasks. This information is provided as part of the input specification: For each robot, you are given a list of all tasks that robot is capable of performing. This project is about getting as many tasks done in a given amount of time by this collection of specialized robots. For all three parts, assume that each task takes one day to perform from start to finish, and once a robot starts working on a task, it completes that task before starting on another task. Also the robots cannot multi-task, i.e. they cannot work on two or more tasks at the same time. For parts 1 and 2, also assume that there are no dependencies among tasks (this makes your life a lot easier!), i.e. any subset of tasks can be worked on concurrently by qualified robots.

1. (a) Suppose your goal is to maximize the number of tasks that can be completed in a single day. Formulate this problem in such a way that one of the graph algorithms covered in class can be applied to solve it.

(b) Write code to solve this problem. Your code should output the maximum number of tasks you can complete in one day, as well as one set of robot-task pairings that will achieve this result. See the coding instructions for more information on writing your code.

2. (a) Suppose your goal is now to minimize the number of days taken to complete all tasks. One way to address this is to apply the solution for 1(a) above to pending tasks at the end of every day. Thus, you do as many tasks as you can on day 1; on day 2, apply the same algorithm but on a reduced" input, where tasks already completed are removed, and so on till all tasks are done. This approach has a greedy flavour to it. Show with the aid of a counter-example that this approach may not always lead to the optimal solution (or prove that it always provides an optimal solution).

(b) Since the problem above seems to be difficult, you instead set an objective of doing as many tasks as possible in a specified number of days, d. Describe how you can conceptually find an optimal solution to this problem. Show the correctness of your algorithm, i.e., argue that the solution will indeed be optimal.

(c) Write code to implement your solution to 2(b) above. You can reuse any code developed for earlier parts of this project. Your code should output the maximum number of tasks you can complete in d days, as well as one set of robot-task pairings for each day that will achieve this result. Hint: Observe that there are only 5 points for this section. That suggests that if you have the code working for problem 1, this would not be much more e ort if you did have a suitable formulation for this problem! Despite this hint, if you were not able to get a suitable formulation for 2(b), then you can do 2(c) by using the approach of 2(a). This is not the desirable option: You will only get half-credit for 2(c) if you do so, but that is better than nothing.

Suppose now that your tasks may have dependencies among themselves. These dependencies are specified by an m*m adjacency matrix A, where a i,j = 1 if task i needs to be completed before task j can be started, and is zero if task j is not directly dependent on task i. Suggest a reasonably efficient way of trying to finish all the tasks in as few days as you can, that builds upon your solutions to the earlier problems. Argue whether your procedure is provably optimal, or just a very good heuristic. No need to write code.

Coding Instructions

  1. You can code in C/C++, Java, or Python. You can use the standard library of whatever language you code in but no other "ready made" code. A part of this project is to get you to implement some of the algorithms that you have seen in class.
  2. Make sure that your code compiles and runs on an LRC machine.
  3. You can use the sample problem specification on Blackboard to test and debug you code. The problem specification consists of three plain text files:

- A robot capabilities le for problems 1(b) and 2(c), the first line of this le specifies n and m as two comma separated numbers. For example, if the first line reads 10; 20, then there are n = 10 robots and m = 20 tasks. All other lines of this le specify a robot and the tasks that robot is capable of performing as a comma separated list. For example, if a line reads 10; 1; 2; 3, then robot 10 is capable of performing tasks 1, 2, and 3. There will be n + 1 lines in this file.

- A task dependencies le for problem 4(c). Each line of this le specifies a dependency between a pair of tasks as two comma separated numbers. For example, if a line reads 1; 2, then task 1 needs to be completed before task 2 can be started. There will be as many lines in this le as there are edges in the dependency graph.

- A task times le for problem 4(c). This le lists the completion times of each task as a comma separated list. For example, if the le reads 2; 4; 6; : : : , then task 1 takes 2 days to complete, task 2 takes 4 days to complete, task 3 takes 6 days to complete, and so on. There will be just one line in this le.

  1. The executable compiled from your code will be called with the le names (that includes the full le path) of these three les as its arguments. The order of these arguments will be the same as the one above. You should print your results to standard out.
  2. Your code will be tested on a different problem specification that will follow the same file formats as the sample specification.
Posted Date: 2/22/2013 12:28:28 AM | Location : United States







Related Discussions:- Program for manage the tasks of a robot, Assignment Help, Ask Question on Program for manage the tasks of a robot, Get Answer, Expert's Help, Program for manage the tasks of a robot Discussions

Write discussion on Program for manage the tasks of a robot
Your posts are moderated
Related Questions
A string S is said to be "Super ASCII", if it contains the character frequency equal to their ascii values. String will contain only lower case alphabets (''a''-''z'') and the asci

how to decode a number from mobile keypad

if age of ram,shayam and ajay are input through keyboard,write a program to determine the youngest of the three.

Purpose This assignment is an exercise in implementing the queue ADT using a singly-linked list. This assignment also introduces the concept of templates. Assignment Th

string S convert it to a palindrome by doing chara, C/C++ Programming

What are the benefits of using friend classes? - Friend classes are useful when a class wants to hide features from users which are required only by another, tightly coupled cl

When I develop a destructor, do I require to explicitly call the destructors for my member objects?

The rPeANUt simulator provides buffering of the characters that are typed into the terminal. However, this would generally not be the case so if the program did not consume a chara


Inheritance and Reuse Consider a car manufacturing company. When they require building a new car, they have two choices. They can start from the scratch, or they can change an