MAST90050调度与优化算法

MAST90050 - Scheduling and Optimisation
Assignment 1 (25%)
Instructions
The assignment must be submitted online via the MAST90050 website before 11:59pm on
Thursday, August 31.
Late submissions are not accepted unless a medical certificate is provided.
Assignments need to be prepared with either Latex or Word. The assignment submission
needs to be one pdf file.
1. Give an instance of 1|prec|Lmax for which a revised version of EDD (only run available jobs)
does not give the optimal schedule.
2. A company assembles different types of cars, and it invests $200,000 to assemble 4 types of
cars for the period of next 18 weeks. The assembly times and the investments required for
each car type are given below.
Car type 1 2 3 4
Time (weeks) 3 4 5 6
Investment ($,000) 35 50 60 55
Th company can get its investment on the car back once it is assembled. How should the
company arrange its assembly schedule in order to minimise its average investment over the
period?
You do NOT need to prove the schedule is optimal.
3. Consider the problem 1|rj , dj = d|Lmax.
(a) Develop an efficient scheduling rule to solve the problem.
(b) Prove that the rule in (a) always delivers an optimal schedule.
(c) What about the optimal scheduling rule that solves the problem 1|rj |Lmax with agreeable
release times and due dates (that is, rj < ri implies dj ≤ di)?
4. Consider the knapsack problem:
Given a set of items, each with a weight and a value, determine which items to include in the
collection so that the total weight is less than or equal to a given limit and the total value is
as large as possible.
1
(a) Show that the knapsack problem reduces to a single machine scheduling problem.
(b) Convert the following knapsack instance to an instance of the scheduling problem in (a).
Item 1 2 3 4 5 6 7 8 9
Weight 1 5 4 3 6 6 4 4 10
Value 6 2 9 6 3 5 9 10 7
The weight limit is 22.
(c) Develop an exact algorithm (e.g., DP, B&B) or meta-heuristic algorithm (e.g., GA, TS,
SA) to find the optimal solution to the scheduling problem for the converted instance in
(b) and implement the algorithm in Python.
Include a printout or screenshot of all code and output(s) at the end of the assignment.
(d) Apply the myopic largest value first (LV) rule to find a solution, and compute the
performance ratio, that is,
G(LV )
G(OPT )
,
where G(·) is the performance measure of the scheduling problem.
How about the smallest weight first (SW) rule?
(e) Any comment on the performance of the three methods?
5. Review, understand, and criticise the literature in Scheduling and Optimisation.
Tasks
(a) Find two scheduling problems. One of them could be related to your group project
topic.
(b) For each of the two scheduling problems, find (≥ 2) relevant scientific articles.
(c) Relate the articles to the content in the course.
(d) Present a compact critical review.
Reporting
Your review should include but is not limited to
– problem description, significance, and application(s)
– solution approach
– limitation(s) of the approach
– extensions (of the problem, of the solution approach, etc.)
Note
– This is an individual assignment, and so no cooperation is allowed.
– The review should be compact and critical, no more than 3 pages.
– The expect outcome is to enhance your ability to understand and criticise the sci-
entific literature in Scheduling and Optimisation.