An algorithm for the maximum revenue jobshop problem

In this paper, we state and study the problem of selecting a product mix and a dispatching rule for a jobshop system to maximize its revenue rate over an infinite planning horizon. We solve the problem of obtaining maximum revenue by selecting a product mix and determine a schedule. The designed algorithm appropriately rounds an optimal solution to a fluid relaxation in which we replace discrete jobs with the flow of a continuous fluid. The algorithm solves the fluid relaxation optimally and then aims to keep the discrete schedule close to the continuous one obtained by the fluid solution. The schedule obtained is cyclic, with bounded WIP and asymptotically optimal. A secondary aim is to further reduce the WIP and the buffers’ sizes by shortening the cycle length. This is achieved at the cost of a slight compromise on the revenue. We report on satisfactory computational results on some benchmark instances.