Free Essay

Operations Research

In: Business and Management

Submitted By poojap17
Words 3078
Pages 13
COMPUTATIONAL COMPLEXITY
OPERATIONS RESEARCH
Pooja Punjabi
Manash Hazarika
INDIAN INSTITUTE OF MANAGEMENT, KOZHIKODE

COMPUTATIONAL COMPLEXITY
Computational Complexity is a measure of the computational time taken by a particular algorithm. In a scenario where there are multiple algorithms available for a particular problem, the effectiveness of any particular algorithm is gauged on the basis of the time constraint. This is done by breaking the algorithm into its basic steps and then taking a count of each of them. Hence greater is the number of steps, greater is the complexity. Now for example, if we take two 5 bit binary numbers and XOR them, the number of steps taken is 5 and if the same process is repeated for a 100 bit binary number, the number of steps goes up to 100. The algorithm employed in either case is the same; the complexity is given by the size of the numbers.
When we say size of a number n, it is defined as the number of binary bits which are required to denote ‘n’ in base 2. For example, 5 in base 10 when expressed in binary takes the form 101, thereby giving n = 3. Similarly 20 is given by 101002 which makes n = 5. Now if we XOR any two numbers each of size n=b, the number of steps taken will be ‘b’. Hence we can say that XORing those numbers has computational complexity of order ‘b’ which is denoted by O(b). This can be applied to even simpler applications like addition wherein if we are to add two n digit numbers, the minimum number of steps taken (ignoring any carry over from the previous step) will be equal to n as we approach from right to left. This can’t be avoided because we need to know every number before we can add them. Coming back to the XOR example stated above, if we are to double the size of the numbers, we will end up doubling the size of the steps required hence increasing the time needed. One important point to take into consideration is that computational complexity is not dependent on the capacity of the machine or in other words, it is independent of implementation. This factor becomes important because different machines may take different times `while processing the same ‘b’ basic steps. Another important point to consider is that for any algorithm with computational complexity defined as O(b), if we are to multiply the size of the problem by X, the computational time will have the same effect of being multiplied by X as well.
Big O notation is used to describe the asymptotic behavior of the functions in complexity theory. It tells you at what rate will the function grow. Rate at which a function grows is called order, hence letter O is used as its notation. Let f(x) and g(x) be two functions defined in real numbers. Then the big O notation would be represented as: f(x) = O(g(x)) (for x belonging to real numbers) if and only if there exist certain constants N and C such that
|f(x)| <= C|g(x)| for all x>N
Basically it means that our function cannot grow faster than the function defining its time dependence complexity.
Commonly used functions as g(x) to describe time dependence are as follows written in increasing order of their growth rate (c is some constant)
O(1) constant
O(log(n)) logarithmic
O((log(n))c) polylogarithmic
O(n) linear
O(n2) quadratic
O(nc) polynomial
O(cn) exponential

As explained above, when it comes to addition, the complexity of adding two binary numbers is given as O(b). However if we are to multiply those numbers, the complexity changes to O(b2). We can take a simple example to illustrate this change. Let’s say we are to multiply two numbers 34 and 56. This will involve multiplication in 4 basic steps and then making carry over adjustments accordingly to get the final result. Hence the complexity for this case becomes O(22). Similarly, if we double the bit size of the numbers to be multiplied, the time required changes to O[(2b)2] = O(4b2).
So complexity theory basically classifies the problems on the basis of the difficulty faced in solving them.

This brings us to the concept of P and NP problems:

1. Deterministic Polynomial-Time (P) Type
A problem is basically classified as that belonging to the P (polynomial time) class if there is at least one algorithm which can solve that problem; the number of steps employed by the algorithm being restricted by a polynomial in ‘n’, where n gives the length of the input used.
An algorithm, existing or newly created is said to abide by polynomial time if, for a given input, the number of steps essential to complete the algorithm is given by O(nk) for some nonnegative integer k, where k gives the complexity of the input provided. Algorithms using polynomial-time are considered to be fast, feasible and efficient. A large number of day to day mathematical applications such as addition, subtraction, multiplication, and division in addition to square roots, logarithms and powers can be performed using polynomial time.
A specific term which comes into being in the deterministic approach is the time complexity of an algorithm. It measures the time taken by any algorithm as a function of the length of the string representing the input provided by the user or any other source.
Time complexity of an algorithm is normally expressed using the Big O notation, as already mentioned above. It does away with all the coefficients and other lower order terms. When an algorithm is expressed in this fashion, we can say that its time complexity has been described asymptotically i.e. its input size has the freedom to approach infinity. To illustrate this point, we can take the help of an algorithm where the time required for all inputs of size n is at most 5n3 + 3n. Hence, the asymptotic time complexity for this algorithm is O(n3)
A few examples of polynomial time algorithms that we find in everyday usage have been given below: * In computer science, the quick sort algorithm when applied on n integers performs at the maximum Cn2 number of operations for a given constant C. Thus the running time is represented by O(n2) which makes it a polynomial time algorithm. * Also as illustrated above, arithmetic operations of the likes of addition, subtraction, multiplication, division et al can be expressed in polynomial time

2. Non Deterministic Polynomial-Time(NP) Type
An NP problem is one which has a solution, inputs to the solution and a verifier which runs in polynomial time. The verifier has to take both the inputs and their corresponding solution into consideration and tell the user whether they are in sync.
NP essentially consists of the set of all decision problems wherein the state of the problem, whether ‘yes’ or ‘no’ has to be supported by efficiently verifiable proofs that it is indeed so. Effectively, these proofs will have to be validated in polynomial time with the aid of a deterministic Turing machine. Defined equivalently in a more formal fashion, NP represents the collection of all such decision problems where the "yes" instances have been accepted in polynomial time by a non-deterministic Turing machine. To gauge the equivalency of the two definitions stated above, we can refer to the fact that an algorithm on such a non-deterministic machine as a Turing machine is divided into two phases - the first phase involves making the nearest possible guess about the solution, which is again generated in a non-deterministic fashion; the second phase makes use of a deterministic algorithm that does the job of verifying or rejecting the guess as made above, as a valid resolution to the current problem
A fantastic example of non deterministic problem solving comes from ‘factoring’ wherein one needs to decide the factors (say a*b=N) of a particular large number N barring the number itself and 1. Theoretical analysts have observed it time and again that if we are to take two numbers of one thousand digits each and multiply them together in a computer, it takes hardly a few seconds to arrive at the result while if we feed this very output to the computer again to get it decomposed into factors, it’s possible that the computer may not figure out an efficient solution for millions of years. This raises the question as to why we need to go through so much of distress to arrive at factors of such a large number. And the answer, as it turns out is of paramount importance with a potential to change the state of an economy. Let’s say one of our friends wants to impersonate a bank. And unlike years back, when the transaction between banks happened in the form of gold bricks transported in trucks, the transactions now are done via online funds transfer through severely protected connections. As it turns out, the encryption algorithm they use to secure their transactions is called RSA. In RSA, each party has a secret key that consists of two numbers p & q – big prime numbers and then they have a public key say n which is equal to p*q. This public key is released to all so that other people are able to send messages via this network, which in turn will be decrypted by the partnering parties using the public key. Now let’s say our friend wants to intervene here. He is in charge of an efficient verifier which is capable of performing large divisions. He has n and then he obtains a Pguess which gives n% Pguess =0

3. Exponential Problems
EXP refers to the set of problems that can be solved in exponential time. Exponential time algorithm is the one in which time is upper bounded by 2poly(n), where poly(n) is a polynomial in n. ie the T(n) is bounded by O(2nk) for some constant k. For eg. N*n chess board problem is EXP type of problem. It cannot be solved in polynomial time.

R refers to problems that can be solved in finite them. These are the problems are basically solvable. R refers to recursive function. The problems can be solved by recursive algorithms in finite time belong to this category. However solvable problems represent a very small part of the problems available with us. The rest of the problems are mathematically unsolvable.

Complexity Analysis of the real life problems:
Step 1: To apply computational complexity in real life, we first need to convert the real life problems into a yes-no problem without altering its complexity. A threshold value in the input is needed for the conversion. The problems are generally of two types- feasibility or satisfice problems. For eg. Scheduling a production facility, timelines and deadlines of the production process and scheduling without delay in jobs. A certain standard examples of real life instances are presented below:

One-Machine Deadline Scheduling Instance: Here we are scheduling the machine operation wrt to its processing time feasibility so that deadlines are met.
Let the processing times be defined as ti and deadlines for the jobs be di where i varies from 1 to n.

Then our problem can be represented as:
Question: Do we have a set of start times si>0 for i varying from 1 to n such that sj does to belong to the set [si, si+ti) where i≠j so that one start time does not clash with another start time under the constraint that it meets the deadlines for each task si+ti <= di ?

Two-Machine Line Balancing Instance: Our task here is to divide the jobs between two machines K and J, evenly when the processing time are known. It can be represented as follows:

Let the set of processing times be ti where i varies from 1 to n. Let there exist a number v
Question: Can we divide the indices i =1 to n such that difference between the time taken by the processes on machine K and the time taken by the processes on machine J be less than or equal to v.

A more restricted version of above problem would be when a perfect balance is required ie v=0.
Then the question would be: Can we divide the indices i =1 to n such that the time taken by the processes on machine K is equal to the time taken by the processes on machine J.
This equal time problem is called two partition problem. This problem is harder to deal with than the two machine line balancing because it is more restricted

Step 2: So the next step we need to understand is how to find the complexity of any problem. So some basic things that contribute to making a problem hard are as follows: when a perfect division of resources is required, sequencing decisions which consider both where you currently are and where you were before, splitting into subsets a set of objects where there exists a constraint for each subset, to find out the largest substructure which satisfies a property, minimizing or maximizing unions and intersections of sets. Substituting the threshold value with a restricted value may also sometimes alter its complexity. So we need to be very careful in doing so. It is important to figure out what makes the problem hard, it may be difficult to get balance fit. Two partition is an example of it. On the other hand, it can be easy for a problem to balance everything but hard to minimize the negative effects of not obtaining the perfect combination. Independent set which requires a maximum size set of vertices of a polygon such that no two of them are connected by an edge is an example of second type. Hence, Identify the type and work accordingly.

As we solve more number of problems, we develop an intuitive ability to recognize the hard part of the problem. Let’s see how to identify a NP hard problem. First identify a hard problem and then think of a easy problem to contrast it. Compare both the problems and identify what makes the hard problem easy. Some examples of constraints are as follows:

Integer Programming (IP) : Maximise c*x subject to a constraint of Ax<=b where x is an integer.
Contrast: Linear programming is easy and so is Integer programming when the constraints have one of two dimensions fixed (unimodular). Dimensions here refer to the no. of variables and total constraints.
Two-machine weighted flow-time minimization: Given two parallel processors and a set of jobs with individual processing times and weights, find a schedule to minimize the weighted sum of completion times.
Contrast: If the given weights or the times are equal then the problem will be easy for any no. of processors. Run equal weights or equal processors constraint one at a time.

Steiner tree: Given a graph G = (V, E), edge lengths, and a subset S of vertices V, find a tree in G of minimum total length that contains S. (The tree may contain vertices in V - S; try connecting the vertices of a square in the plane.)
Contrast: The minimum spanning tree problem, in which S =V, is easy.

Normally the hard problems can be solved with dynamic programming. If dynamic programming does not help then other methods like off the shelf mathematical software’s or heavy-duty mathematical programming methods and heuristics can help.

Easy problems can be solved using linear programming, simplex methods and integer programming etc.

Reductions:
In computational complexity, reduction is defined as transforming one type of problem into another. A problem X is reducible to problem Y if X’s algorithm can be used to solve Y too. This means that problem Y is easier to solve than X. There are two types of reductions that we use: many-one reduction and the Turing reduction. A many to one reduction is done by mapping instances of a problem into the instances of other problem. Turing reduction on the other hand works by solving one problem assuming that the other problem is easy. Turing reduction is stronger than many-one reduction. However, stronger reductions are not effective in separating problems though they are easier to design.

Reductions are useful when they are easy. Take for instance, a difficult NP-complete problem can be reduced to a trivial problem. Also, it can convert an incomputable problem to a decidable one. Reduction is used in problems like halting problem to prove that language is not decidable ie the turing machine M would halt when input of string w is given(H(M,w)). This language is said to undecidable. Now if F(M) is the problem of determining the whether the input language to the turing machines is empty or not then we know by reduction from H that F is undecidable.

Conclusion:
Basic understanding of computational complexity helps a manager to determine the time he would take to solve the real life problem at hand and judge how large the instance of problem actually is. Also, choice of algorithm is more important than the choice of hardware and data structures. Classifying the problems as easy of NP-hard will tell us the available methods to solve it. Deciding the final method can then be done looking at other aspects also like size, financial stake, desirable accuracy and time constraints. Computational complexity is an ineluctable phenomenon. Most problems are hard to solve. But realistic cases are almost easy every time if we study them hard enough. As a manager, the basic learning and application of computational complexity helps us majorly in problems related to operations. As in the above text certain examples like machines scheduling, meeting deadlines, minimizing late jobs have been cited, similarly we can use it for problems in our production facility and reduce the time to solve by using appropriate methods available for a particular type of complexity.

REFERENCES:

* http://en.wikipedia.org/wiki/Computational_complexity_theory * http://theory.stanford.edu/~trevisan/notes/complexitynotes02.pdf * http://www2.isye.gatech.edu/~ctovey/tovey.tutorial.pdf * http://staff.science.uva.nl/~ulle/teaching/comsoc/2012/slides/comsoc-complexity-tutorial.pdf * Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak

Similar Documents

Premium Essay

Operations Research

...PRINCIPLES AND APPLICATIONS OF OPERATIONS RESEARCH * Jayant Rajgopal Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania ABSTRACT This chapter will provide an overview of Operations Research (O.R.) from the perspective of an industrial engineer. The focus of the chapter is on the basic philosophy behind O.R. and the so-called “O.R. approach” to solving design and operational problems that industrial engineers commonly encounter. In its most basic form, O.R. may be viewed as a scientific approach to solving problems; it abstracts the essential elements of the problem into a model, which is then analyzed to yield an optimal solution for implementation. The mathematical details and the specific techniques used to build and analyze these models can be quite sophisticated and are addressed elsewhere in this handbook; the emphasis of this chapter is on the approach. A brief review of the historical origins of O.R. is followed by a detailed description of its methodology. The chapter concludes with some examples of successful real-world applications of O.R. * Maynard's Industrial Engineering Handbook, 5th Edition, pp. 11.27-11.44. 1.1 INTRODUCTION Although it is a distinct discipline in its own right, Operations Research (O.R.) has also become an integral part of the Industrial Engineering (I.E.) profession. This is hardly a matter of surprise when one considers that they both share many of the same objectives, techniques and application......

Words: 11680 - Pages: 47

Free Essay

Operations Research

...Year | 2015-16 | Academic Term | T1☐ T2☐ T3☐ T4☐ T5☐T6☐ | Functional Areas | OPERATIONS MANAGEMENT | Core ☐ Elective x☐x | Title | Quantitative Methods II | Abbreviation | QM-II | Course Coordinator | Prof. RAVI SHANKAR | Teaching Members | | Course Revision Record Version | Version Date | Recommendation | 1 | 05 Sept 2015 | | Credits | 3 | Contact Hours | 30 | Learning Hours | 60 | Office Hours | 30 | Contact Details | 09811033937 | Course eMail | r.s.reaches@gmail.com | Course Descriptor Course Overview(200 words) | Quantitative Methods-II, focuses on ‘Operations Research’ tools which helps in solving problems in different functional domain of business. It also helps to optimize business operations/processes. The Quantitative Method-II tools act as aids to decision makers to take best decision for effective & efficient use of resources which ultimately lead to profit maximization or to achieve multiple goals or objective. | Course must be aligned with a strategic objective of the program Prerequisites/Co-requisites | Quantitative Methods I | Learning Objectives | To learn basic optimization techniques and their managerial applications with a focus on methodologies such as Linear Programming, Transportation models, Assignment Models, Transhipment Models, Games Theory, Queuing Models, Goal Programming, Integer Programming, Non-linear Programming, Simulation and Decision Theory. | Learning objectives must be aligned with......

Words: 1342 - Pages: 6

Premium Essay

Operations Research

...weekly meeting will be scheduled at which time students may ask questions, discuss homework exercises, etc. Attendance at this meeting is optional. Grading System • There will be 2 examinations, one at the middle of the course, and one at the end. • Homework will be assigned each week, but this will not be given to the instructor to be graded. Students are encouraged to work together on homework assignments. • There will be a short (multiple choice) quiz each week which tests whether you have understood the homework assignment. Only the best 10 quizzes for each student will be used in computing the course grade. Midcourse Examination Final Examination Weekly Quizzes (best ten) 30% 50% 20% page 3 What is “Operations Research”? • other names: management science, decision science • application of information technology for decision-making • designing systems to operate in the most effective way or deciding how to allocate scarce human resources, money, equipment, or facilities • closely related to several other fields: o applied mathematics, o computer science, o economics, o industrial engineering, and o systems engineering page 4 Typical problems faced by an O.R. practitioner: • In what sequence should parts be produced on a machine in order to minimize the change-over time? • How can a dress manufacturer lay out its patterns on rolls of cloth to minimize wasted material? • How many elevators should be installed in a new......

Words: 508 - Pages: 3

Free Essay

Operation Research & Methods

...Operational Research Models and Methods in CIM1 Abstract : Many models and methods of Operational Research can be adapted for industrial applications. In this chapter, we show on one hand the main problems of a manufacturing system and, on the other hand, how they can be ranged in a hierarchical order, derived from a CIM architecture (from the strategic decisions to the production constraints). Then, we present an Operational Research tool for solving each of these problems. 1 Introduction Flexible Manufacturing Systems (FMS) are nowadays installed in the mechanical industry, especially in car factories. However, the market constraints impose to always improve the production system and the whole production organization. The concepts developed by Taylor and applied at the beginning by Ford are progressively abandoned and replaced by the Just-In-Time concept and the Computer Integrated Manufacturing philosophy (CIM). One of the aims of the CIM philosophy is to provide an integrated information system which avoids the rigid separations between the different functionalities of a complete production system. With such integrated information systems, the loss of time on one hand between the customer order and the part delivery, on the other hand between the product design and its manufacture will be drastically reduced. To understand the complete production system, it is relatively easy to find in the scientific literature excellent general books explaining the different......

Words: 5165 - Pages: 21

Premium Essay

Assignment @ Operation Research

...ASSIGNMENT ON OPERATION RESEARCH ( FIN – 3104 ) 3RD YEAR , 1ST SEMESTER BBA – 3RD BATCH DEPARTMENT OF FINANCE JAGANNATH UNIVERSITY TOPIC Quantitative Analysis for Optimization : Using Linear Programming & Transportation Problem Group Name Name & ID No. of the Group Members: |Sl. No. |Name |ID No. | | | | | |01 |Suman Chandra Mandal (Group Leader) |091557 | | |Md. Nahid Islam |091604 | |02 | | | | | | | |03 |Mahbuba Mehreen |091619 ...

Words: 1940 - Pages: 8

Premium Essay

Operation Research Development

...Operations Research OR - Development of OR - England , world war  → determining the last utilization of limited resources - USA → 1947 → simplex method - Development → computer science - OR models mathematical model → variables, Function Optimal solution according to different techniques Simulated model → study for a specific system at Certain time period and simulate this system Heuristic model → empirical rules to find Approximate solution from point to another in the System Mathematical Model 1- Decision variables and parameters unknown values we need to solve equations to get these values EX: parameter → determine system We need to determine level of production for a specific good based on raw material, machine capacity Unknown parameter→ level of production, Unknown variable → number of units produced 2- Constraints or restrictions → row material 3- Objective function → EX: profit function maximization cost function Minimization EX: production planning machine 1 2 3 Profit/unit Time per unit (minutes) Machine Product1 product2 product3 capacity 1 2 1 430 3 0 2 460 1 4 0 420 3 2 5  OR mathematical model X1 → amount product1 X2 → amount product2 X3 → amount product3 Profit function: Constraints 1x1 + 2x2 + 1x3 ≤ 430 3x1 + 0x2 + 2x3 ≤ 460 1x1 + 4x2 + 0x3 ≤ 420 Additional non negativity constraints x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0 We are looking for optimum sol for x1 , x2 , x3 to maximize objective function subject to constraints Introduction to optimization &......

Words: 1272 - Pages: 6

Premium Essay

Operations Research and Its Prospects in Pakistan

...Operations Research and its Prospects in Pakistan Prof. Dr. Shoaib ud Din Mathematics Department Punjab University, Lahore, Pakistan Operations Research has had an increasingly great impact on the management of organizations in the recent years. In fact, with the exception of advent of electronic computer, the extent of this impact seems to be unrivalled by that of any other recent development. However, all the development in this field has gone almost unnoticed in most developing countries including Pakistan. This article is an effort to introduce Mathematics community in the country to the subject and its achievements. A brief history In order to appreciate the importance of OR in the world today it is important that we know something of its history and evolution. Although roots of Operations Research can be traced back many decades, it is generally agreed that this discipline began during World War II. During the War team of British scientists with diverse background were called upon to study the strategic and tactical problems associated with air and land defense of the country. The establishment of this scientific team marked the first formal Operations Research activity. Their efforts were allegedly instrumental in winning the Air Battle of Britain, The Island Campaign in the Pacific, the Battle of the North Atlantic, and so on. The name Operations Research-Operational Research in the United Kingdom – was apparently coined because the problems assigned to this......

Words: 1347 - Pages: 6

Premium Essay

Development of Transportation Methodology in Operation Research

...ADVANCED OPERATION RESEARCH ASSIGNMENT OF O.R. METHODOLOGY DEVELOPMENT DEVELOPMENT OF TRANSPORTATION METHODOLOGY IN OPERATION RESEARCH “PENGEMBANGAN METODE TRANSPORTASI DALAM OPERASI PENELITIAN” TYPE II – COMPARE & CONTRAST IQBAL TAWAKKAL - 1506694736 PROGRAM MAGISTER TEKNIK INDUSTRI - SALEMBA UNIVERSITAS INDONESIA 1. INTRODUCTION A special class of linear programming problem is Transportation Problem, where the objective is to minimize the cost of distributing a product from a number of sources (e.g. factories) to a number of destinations (e.g. warehouses) while satisfying both the supply limits and the demand requirement. Because of the special structure of the Transportation Problem the Simplex Method of solving is unsuitable for the Transportation Problem. The model assumes that the distributing cost on a given rout is directly proportional to the number of units distributed on that route. Generally, the transportation model can be extended to areas other than the direct transportation of a commodity, including among others, inventory control, employment scheduling, and personnel assignment. Transportation was one of the earliest application areas of operations research, and important transportation problems, such as the traveling salesman problem, vehicle routing problem, and traffic assignment problem, contributed to fundamental knowledge in operations research. Transportation remains one of the most important and vibrant areas of......

Words: 2523 - Pages: 11

Premium Essay

Deterministic Operations Research Homework Answers

...MIS 208 SPRING 2015 HOMEWORK 1 (due 13:15 on Monday, 6 April 2015, in class at 101) Reading Assignment: Please read section Duality and Sensitivity Analysis of the text book Winston. You will be responsible on that section in the exam. Question 1: Two different products, P1 and P2 can be manufactured by one or both of two different machines, M1 and M2. The unit processing time of either product on either machine is the same. The daily capacity of machine M1 is 200 units (of either P1 or P2, or a mixture of both) and the daily capacity of machine M2 is 250 units. The shop supervisor wants to balance the production schedule of the two machines such that the total number of units produced on one machine is within 5 units of the number produced on the other. The profit per unit of P1 is $10 and that P2 is $15. Set up the problem as an LP in equation form. Question 2: A company manufactures purses, shaving bags and backpacks. The construction includes leather and synthetics, leather being the scarce raw material. The production process requires two types of skilled labor: sewing and finishing. The following table gives the availability of the resources, their usage by the three products, and the profits per unit. a) Formulate the problem as a linear program and find the optimal solution by using appropriate Simplex Methods that you have seen in the class b) From the optimum solution determine the status of each resource. Question 3: The following......

Words: 480 - Pages: 2

Premium Essay

Operations Research

...Business Research Methods (BRM) Project submission on Meru Cabs: Why is this cab service provider losing market share? Submitted by: Group 8 Submitted by: Group 8 Aditi Chaudhary | PGP/19/183 | Alka | PGP/19/186 | Alla Bharath Reddy | PGP/19/187 | Avishek Pandey | PGP/19/196 | Miranda Boro | PGP/19/207 | Md. Talha | PGP/19/208 | Declaration "We hereby declare that this submission is our own work and that, to the best of our knowledge and belief, it contains no material previously published or written by another person nor material which has been accepted for the award of any other degree or diploma of the university or other institute of higher learning, except where due acknowledgment has been made in the text.” Contents Introduction 1. Business Research problem 2. Why did we select it? 3. Introduction 4. Research Methods 5. Information regarding collection of data a. Quantitative b. Qualitative 6. Research Methodology c. Survey d. Focus Groups Discussions 7. Expected analysis and outcome Conclusion Business Research problem: “Why is Meru cabs losing its market share? “ The overall bookings are very less on Meru as compared to its competitors and it is lagging behind low-cost cab service providers such as Ola, Uber and Taxi for sure. Our present research proposal addresses this issue and tries to find out the reasons behind the same. Why did we select it? Many of our team......

Words: 1548 - Pages: 7

Premium Essay

Operation Management

...Journal of Business & Economics Research – July 2005 Volume 3, Number 7 Operations Research And Operations Management: From Selective Optimization To System Optimization Jack A. Fuller, (E-mail: jfuller@wvu.edu), West Virginia University C. Lee Martinec, West Virginia University ABSTRACT The focus of this research paper is to discuss the development of Operations Management (OM) and Operations Research (OR) with respect to their use within the organization’s decision-making structure. In addition, the difference in the tools and techniques of the two fields is addressed. The question is raised as to how distinct the two academic fields have become in light of the application of their models to the service industry. Suggestions are made regarding the possibility of incorporating OM/OR models and their output into the decision making structure of the organization towards the goal of “system optimization”. ORIGINS OF OPERATIONS MANAGEMENT AND OPERATIONS RESEARCH A comparison of the origins of operations management and operations research reveals that both are an innovation of the 20th century. The origin of operations research was in England, circa 1937, and has its roots in scientific management, with its first significant applications to military operations in both World War I and World War II. Operations management had its origins in the early factory system, and was more associated with physical production in a factory environment and it too was strongly......

Words: 2973 - Pages: 12

Premium Essay

Master in Business Management

...OPERATION RESEARCH Credits: 4 SYLLABUS Development Definition, Characteristics and phase of Scientific Method, Types of models. General methods for solving operations research models. Allocation: Introduction to linear programming formulation, graphical solution, Simplex ethod, artificial variable technique, Duality principle. Sensitivity analysis. Transportation Problem Formulation optimal solution. Unbalanced transportation problems, Degeneracy. Assignment problem, Formulation optimal solution, Variation i.e., Non-square (m x n) matrix restrictions. Sequencing Introduction, Terminology, notations and assumptions, problems with n-jobs and two machines, optimal sequence algorithm, problems with n-jobs and three machines, problems with n-jobs and m-machines, graphic solutions. Travelling salesman problem. Replacement Introduction, Replacement of items that deteriorate with time – value of money unchanging and changing, Replacement of items that fail completely. Queuing Models M.M.1 & M.M.S. system cost considerations. Theory of games introduction, Two-person zero-sum games, The Maximum –Minimax principle, Games without saddle points – Mixed Strategies, 2 x n and m x 2 Games – Graphical solutions, Dominance property, Use of L.P. to games, Algebraic solutions to rectangular games. Inventory Introduction, inventory costs, Independent demand systems: Deterministic models – Fixed order size systems – Economic order quantity (EOQ) – Single items, back......

Words: 30976 - Pages: 124

Premium Essay

Material Purchasing Factors That Impact on Food Production

...CHAPTER ONE INTRODUCTION OF THE STUDY 1.1 Introduction This chapter introduces the material purchasing factors that impact on food production in hotel industry. The chapter also gives some background information about Ambassadeur Hotel; it outlines the statement of the problem, research objectives, research questions, significance, limitations, assumptions and scope 1.2 Background of the study Material purchase for food products is a function concerned with the search, selection, receipt, storage and final use of a commodity in accordance with the catering industry policy of the establishment. Business strategy literature is replete with evidence that indicate the purchasing methods of a firm have an impact on achieving a firm’s goals. The purchasing function can have an impact on the firm’s ability to achieve its chosen strategies because organizational buying is one of the forces that impact competition (Carr et al. 2000; Landeros and Monczka 1989). As hotels strive to achieve global competitiveness, effective purchasing has assumed great importance. According to Carter and Narasimhan (1996), firms need to recognize the strategic role of purchasing as well as the impacts that it exerts on organizations. The relevance of effectively managing the material resources of an organization to its competitive success has been observed by both practitioners and researchers in purchasing and supply management. As a result, purchasing has evolved in many firms from a low-skill,......

Words: 10630 - Pages: 43

Free Essay

Indian Economy

...Applications of Operations Research planning, routing, scheduling, forecasting, process analysis and decision analysis. OR is also contributing greatly to healthcare services such as surgical and bed scheduling, portering operations, emergency transport, accident trend analysis and treatment optimization. In the service sector, OR techniques have been found especially helpful when dealing with variability in service delivery such as call centres, queues for service and medical wait times. A sampler of typical OR applications includes: • • • • • • • • • • • • Optimization of LTL trucking (Yellow Freight) Optimal package designs (Domtar Packaging, Ltd) Manpower planning models (Treasury Board Secretariat) Aircraft operations (Delta Airlines) Surgical bed optimization (Fraser Health Authority) Pre-board passenger screening (Vancouver International Airport ) Switching network studies (Bell-Northern Research, Ltd) Maintenance Strategies for the US Coast Guard Revenue Management (American Airlines) Resource allocation in a mental health hospital (Douglas Hospital) Routing of Waste Trucks (Waste Management Inc.) Rail Car Optimization (CP Rail) Successful OR applications can be found in a broad array of industries dealing with challenges such as OR has been applied in many industry sectors including the following: Transport and Travel. OR techniques are used by airlines and rail companies to offer varying fares and make higher revenues by filling more seats at different prices -......

Words: 414 - Pages: 2

Free Essay

Production and Operations Management

...Brief History of the Production and operations Management function by V S Rama Rao on January 24, 2009 At the turn of the 20th century, the economic structure in most of the developed countries of today was fast changing from a feudalistic economy to that of an industrial or capitalistic economy. The nature of the industrial workers was changing and methods of exercising control over the workers, to get the desired output, had also to be changed. This changed economic climate produced the new techniques and concepts. Individual Efficiency: Fredric W Taylor studied the simple output to time relationship for manual labor such as brick-laying. This formed the precursor of the present day ‘time study’. Around the same time, Frank Gilberth and his leaned wife Lillian Gilberth examined the motions of the limbs of the workers (such as the hands, legs, eyes etc) in performing the jobs and tried to standardize these motions into certain categories and utilize the classification to arrive at standards for time required to perform a given job. This was the precursor to the present day ‘motion study’. Although to this day Gilberth’s classification of movements is used extensively, there have been various modifications and newer classifications. Collective Efficiency: So far focus was on controlling the work output of the manual laborer or the machine operator. The primary objective of production management was that of efficiency – efficiency of the individual operator. The......

Words: 745 - Pages: 3