I've read through several books/papers on optimization, where in particular I came across the term $\textit{Greedy Heuristic}$ in a few of the books/papers on discrete optimization. How does one derive such a heuristic for an optimization problem, and how do we use the heuristic to solve the problem?
I've only managed to find one such example which came in the form of a question from a book (without answers provided sadly). The problem is stated as follows:
$\textbf{Q:}$ Consider the following private-hire contract optimization problem:
The company created a forecast for a period of six months, for the required number of cars needed per month - $\textbf{Jan}$: 40, $\textbf{Feb}$: 25, $\textbf{Mar}$: 36, $\textbf{Apr}$: 37, $\textbf{May}$: 30, $\textbf{Jun}$: 35.
Also, the cars were rented on contracts with fixed prices as follows - 3-month contracts at 8000 per car, 4-month contracts at 9000 per car, and 5-month contracts at 10000 per car.
Furthermore, 6 cars are avaiable for use from the previous period, and their contract expires by the end of Feburary. The manager of the company needs to know how many contracts of each type are needed at the start of each month in order to satisfy the forecasted number of cars for the next six-month period.
$\textbf{Objective:}$ To minimize cost, and to have no cars on contract at the end of June.
$\textbf{Query:}$ As stated in the first few lines of my post, how can I derive such a heuristic for the above problem as an example, and how can one use it to solve the problem?
Heuristics (as opposed to metaheuristics) are often (usually?) created based on some intuition into good solutions or some specific aspect of the problem structure. The term "greedy heuristic" actually refers to a class of heuristics, which in general terms go along the following lines: make the first decision based on getting the best "bang for the buck"; recalculate where you are at (needs, capacities, etc.); make the next decision to get best "bang for the buck"; repeat.
So a greedy heuristic for your problem might look like the following. Use as many five month contracts as it takes to cover January demand (after netting out left over contracts). Figure the revised net demand for February and cover that with five month contracts. Repeat for March, only now using four month contracts. In April, add as many three month contracts as it takes to cover the rest of the period.
A fancier heuristic might start with that and look for places where a cheaper contract could be switched for a more expensive one (do it if the solution remains feasible, don't do it if it leaves uncovered demand).