Abstract:

A class of flexible flow-shop scheduling problem with due-dates is studied by using cooperative games theory. In this problem, jobs with an initial scheduling order need to be processed successively on multiple processes. There are multiple identical parallel machines at each processing stage. The cost of customer who owns one job is the sum of the job's weighted completion time and tardiness penalty. The scheduling objective is to minimize the sum of customers' costs. Considering that customers can collaborate to form coalitions and reschedule within coalitions to save costs, a cooperative game model is established. In this model, the customers can be seen as the players and the maximum cost savings obtained by rescheduling can be seen as the characteristic function. By analyzing the properties of cooperative games, the reasonable allocations of cost savings are used to reduce the customer's cost. When the jobs have identical processing time on the same processing stage and common due date, it is proved that the corresponding cooperative games are convex. Core allocations can be obtained by the $\beta$ rule and the Shapley value, and the Shapley value can be expressed in a simple form. Examples are given to verify the properties of the cooperative games and rationality of the cost allocation methods.

Key words: flexible flow-shop, cooperative games, due date, β rule, core allocation