Cash management in single and parallel machine scheduling

Abstract

Traditional scheduling problems are usually focused on minimising time-based objectives. In this paper, we have examined the problems in single and parallel machine scheduling. We have incorporated cash management into the objective function of these problems. It is assumed that processing a given job involves incurring a total cost and receiving a total revenue. Each job also has its own temporal pattern of cost incurring and revenue receiving. Nonetheless, the total cost/revenue of processing a job is assumed to be incurred/received during its processing and not beyond it. We have defined five new objectives: (i) maximising average available cash; (ii) minimising revenue-cost duration; (iii) minimising average cash deficiency; (iv) minimising maximum cash deficiency; and (v) maximising minimum available cash. Based on the results achieved in this paper, the above patterns do not affect the optimal scheduling policy in regards to the first two objectives. For single machine models, all except one of the problems are solved in polynomial time. For parallel machines, all models are proved to be NP-hard. Some of the NP-hard models are convertible to equivalent traditional ones.

Keywords:

• scheduling
• single machine
• parallel machine
• cash management
• cash deficiency
• duration