The University of Edinburgh First Semester, 2017-18
Scientific Computing代写 The strict deadline for submitting the assignment is 18:00 on 29 November, 2017.Using “Multiple File Upload”, upload
COMPUTING FOR OR AND FINANCE
Homework Assignment for Scientific Computing
Total Marks: 100
Instructions Scientific Computing代写
1.The strict deadline for submitting the assignment is 18:00 on 29 November,2017.Using “Multiple File Upload”, upload on Learn under Homework Assignment all files that you wrote one by one, including the pdf file of your report.Each file name must start with your UUN, e.g., s1234567_report.tex.
- This is an individual assignment and not a group
- You should attempt all questions.
- Apart from implementing several functions in Matlab, you are asked to write a report of yourwork using LATE
Add a title page to your report, including your full name, UUN, and the date of submission. Choose an appropriate title.
Use the same numbering for your answers as for the questions and add a table of contents. Try to explain what your are doing in a concise but reproducible way. Write full sentences!
- Ifrequested, use LATEX’s verbatim environment to include the Matlab codes in your docu- The codes must be included under the respective questions.
- Addcomments to your Matlab code and try to write your programs as simple and efficient as Marks will be deducted if comments are missing or functions and algorithms are unnecessarily complicated.Scientific Computing代写
All submissions will be processed by Turnitin to check for plagiarism.
Storage Allocation
Youhave just been contacted by an old friend who manages the warehouse of a small wholesaler. One of the tasks your friend has to deal with is to decide where each item of the wholesalers assortment of goods is stored in the warehouse. This is an eminent task, as it has a massive impact on the most labour intensive activity inside a warehouse: the retrieval of individual items from their respective storage places. This activity is triggered by customers ordering products from the wholesaler.Scientific Computing代写
Given a customer order, a staff has to walk into the warehouse with a trolley to pick the individual items of the order from their respective storage places. After the staff has picked allitems, he walks back to the packaging zone and puts them all into an appropriately sized cardboard box. Typically, the packaging zones are located alongside a conveyor belt or next to the docking bay for lorries. In this context, an item is also called a stock keeping unit (SKU) and the staff arecalled pickers. The challenge is now to decide where to store each SKU in the warehouse such that the total walking distance for the pickers is minimal.
The current storage space allocation has “grown” over time and your friend is exceedingly unhappy with it, presuming that she could do much better with an “optimised” allocation. Can you help her?
The setting for her problem is as follows: Scientific Computing代写
- Thewholesaler’s assortment of goods comprises 90 product groups, numbered from 1 to 90
- The warehouse is partitioned into 90 storage places (or shelves), numbered 1 to 90, and eachstorage place can hold exactly one product We can assume that shelves are big enough to store “everything” of that group. The warehouse floor plan is sketched below.
Each storage place has a width of 3 meters and depth of 2.5 meters, and the corridor has a width of 5 meters. The only entrance to the warehouse is at the bottom left.
The figure also shows the location of the packaging zone, which is 10 meters away from the warehouse entrance.
- Each customer orders consists of items from at most three different product groups, i.e.,a picker has to visit up to three shelves on his
For simplicity, I will identify product groups with SKUs in the following. Moreover, I will call an allocation of SKUs to shelves a storage space allocation or, simply, a solution.Scientific Computing代写
Available Material Scientific Computing代写
I have uploaded a zip file containing
- a CSV file that contains the matrix of distances within the warehouse, i.e., between the different storage places as well as from the packaging The first row and column containsthe shelf number, and the last row and column contains the distances to and from the packaging zone to a shelf (only measured from the entrance door into the warehouse). Note that the distance calculations are a bit “rough”, but they serve the purpose.
- a CSV file that contains the current storage allocation. The first row of the table is the shelf numberand the second row the item number stored in that
- a CSV file that contains a list of 3,000 customer orders. The orders are numbered from 1 to 3,000 (column 1) and contain the indices of the SKUs of the order (columns 2, 3 and 4). If theorder comprises less than three SKUs, the row is filled up with
In the following, you will have to develop and implement a method that provides a – hopefully – better allocation.
Questions Scientific Computing代写
(1)Explainthe problem your friend is facing in your own words in the You can use the same picture that I have used (also included in the zip file).[5]
(2)Write a user-defined function that computes the total distance walked by the pickers towork off a given list of orders.
Try to make your function as flexible as possible and add comments.
(3)Test your function with the current allocation and include the computed total walking distance in your report.[20]
Now that you have a function to compute the distance of a given storage space allocation, you can start to optimise. Methods that try to improve a given solution are often called improvementmethods.Scientific Computing代写
A simple idea to try to improve a given allocation is to pick two shelves and simply swap their SKUs. If the swap would reduce the total walking distance, we implement it, i.e., we carry out the swap. If not, we discard the pair and consider another one.
Example of Swapping. For the following allocation (using only 10 items and shelves)
swapping the SKUs of shelves 4 and 7 gives us the new allocation
There exist many different ways to exploit this idea. Two fairly straight-forward improvement methods are complete enumeration and random selection.
(a)Incomplete enumeration, we go over all distinct pairs of storage spaces and for each pair, we swap the two corresponding items and then compute the new distance after the After having considered all pairs, if we have found a pair that decreases the total walking distance, we implement this swap. If there is more than one such pair, we pick the one with the highest decrease in distance. In both cases, we start the procedure all over, i.e., we again go over all distinct pairs of shelves. The method stops if no pair was found that reduces the total walking distance.Scientific Computing代写
Write a user-defined function that implements this method. Add comments to your func- tion.
Apply the function to the currently used storage space allocation, using the full set of orders, and store the computed allocation in a CSV file.
(1)In your report, briefly explain what you did. Also include the new allocation as a table, together with its total distance and the run time of your function.[15]
(b)Whilecomplete enumeration often provides high quality solutions, going over all pairs can be very time consuming. An alternative to that is random selection. In this method, we pick a random pair of storage spaces, swap the two corresponding SKUs, and then compute the new total walking distance after the swap. If this swap reduces the distance, then we carry it If not, then we pick another random pair. The method stops if no improvent could be achieved for kmax consecutive iterations (where one iteration consists of picking one random pair of shelves).
Write a user-defined function that implements this method. Add comments to your func- tion.Scientific Computing代写
Apply the function to the currently used storage space allocation, using the full set of orders, and store the computed allocation in a CSV file.
Pick a suitable value for kmax yourself and explain in your report how you chose this value. Also briefly explain what you did and include the new allocation as a table, together with its total distance and the run time of your function in your report.[15]
(c)Compare the two methods of complete enumeration and random selection. Which one performsbetter (on average), e., which one provides (a) better solution(s)?
In your report, briefly explain what you did and include a numerical comparison of the solutions provided by the two methods.[5]
(4)Improvementmethods often struggle to perform well if they start off from a bad initial solution (without going into details of how to quantify “well” and “bad” in this context). As an alternative, often one or more initial solutions are constructed from scratch by some other means, serving then as the starting point for the improvement methods. Methods that try to generate an initial solution are also called construction methods.
The simplest idea for such a construction method is to allocate items to shelves randomly.Scientific Computing代写
Write a user-defined function that creates random storage space allocations. Add comments to your function.
Use your function to create a set of initial solutions for the problem using the full set of orders. Pick the best one and store it in a CSV file.
In your report, briefly explain what you did. Also include the best allocation as a table, together with its total distance and the run time of your function.[10]
(5)Feed the solution you obtain in part (4) to the two improvement Could you find a better solution?
In your report, briefly explain what you did and include a numerical comparison of the solutions.[10]
(6)In a last step, we want to predict how well allocations derived from the above methodology performin the future, e., for yet unseen sets of orders. To do that, use the concept of training, validation and test sets.
Explain in your report how you split the set of orders into these three sets and for which purpose you used each set.
Moreover, include the experimental results in your report and give an estimate of how well the chosen method performs for unknown order sets.
Based on that recommend an allocation to your friend. Also explain to her why you chose it and which methodology she should use in the future, if allocations have to be recalculated.[15]
The remaining five marks will be awarded based on the layout and style of your pdf and your proficiency with LATEX.[5]
Bonus Question: Construction Methods
While random generation is a generic approach that works for many problems and has the potential of providing very good solutions (even the optimal one), methods that are specially tailored to a specific problem often provide, on average, much better initial solutions. Can you think of an alternative way of constructing an initial storage space allocation? If yes, implement the method.Scientific Computing代写
In your answer, describe the method you devised and explain its motivation. Moreover, compare the quality of the allocations it provides with those of random generation. Include the comparison in your answer and give a recommendation which one should be used preferably[15]
