An Optimization Problem on Two-Partition of Jobs for Profit Allocation

This paper addresses a discrete optimization problem involving a new game situation, where after two manufacturers have jointly contracted with a customer for processing n non-preemptive jobs owing to their insufficient operation facilities, they need to bargain on a two-partition of these jobs to obtain a profit distribution reasonable and acceptable for each manufacturer. The profit in processing the jobs assigned to each manufacturer in one partition is related with an optimal schedule for minimizing a common cost function on job schedules. This discrete game situation is an extension of the original Nash bargaining model (NBM) which is formulated to a continuous optimization problem. In this paper the continuous optimization problem, whose solution is the famous Nash bargaining solution (NBS), is revised in order to design a valid solution scheme for profit allocation of our situation. A novel dynamic programming algorithm for this extended problem is developed for a type of special cases