Cooperative Game Theory Based Coordinated Scheduling of Two-Machine Flow-Shop and Transportation

A cooperative game theoretical approach is taken to production and transportation coordinated scheduling problems of two-machine flow-shop(TFS-PTCS problems)with an interstage transporter.The authors assume that there is an initial scheduling order for processing jobs on the machines.The cooperative sequencing game models associated with TFS-PTCS problems are established with jobs as players and the maximal cost savings of a coalition as its value.The properties of cooperative games under two different types of admissible rearrangements are analysed.For TFS-PTCS problems with identical processing time,it is proved that,the corresponding games areσ_(0)-component additive and convex under one admissible rearrangement.The Shapley value gives a core allocation,and is provided in a computable form.Under the other admissible rearrangement,the games neither need to beσ_(0)-component additive nor convex,and an allocation rule of modified Shapley value is designed.The properties of the cooperative games are analysed by a counterexample for general problems.

Makespan Minimization in Two-Machine Flow-Shop Scheduling under No-wait and Deterministic Unavailable Interval Constraints

This paper systematically studies the two machine flow-shop scheduling problems with no-wait and deterministic unavailable interval constraints.To minimize the makespan,three integer programming mathematical models are formulated for two-machine flow-shop with no-wait constraint,two-machine flow-shop with resumable unavailable interval constraint,and two-machine flow-shop with no-wait and non-resumable unavailable interval constraints problems,respectively.The optimal conditions of solv-ing the two-machine flow-shop with no-wait constraint problem by the permutation schedules,the two-machine flow-shop with resumable unavailable interval constraint problem by the Johnson algorithm,and two-machine flow-shop with no-wait and non-resumable unavailable interval constraints problem by the Gilmore and Gomory Algorithm(GGA)are presented,respectively.And the tight worst-case performance bounds of Johnson and GGA algorithms for these problems are also proved to be 2.Several instances are generated to demonstrate the proposed theorems.Based on the experimental results,GGA obtains the optimal solution for the two-machine flow-shop with no-wait constraint problem.Although it cannot reach the optimal solution for the two-machine flow-shop with resumable unavailable interval constraint problem,the optimal gap is 0.18%on average when the number of jobs is 100.Moreover,under some special conditions,it yields the optimal solution for the two-machine flow-shop with no-wait and non-resumable unavailable interval constraints problem.Therefore,GGA is an efficient heuristic to solve these problems.

A HEURISTIC FOR F3/bi= b/C_(max) AND ITSWORST-CASE ANALYSIS

This paper describes a heuristic for solving F3/bi = b/Cmax scheduling problem. This algorithm first uses the Johnson’s algorithm solving F2Cmax, then, presents revised algorithm to solve F3/bi = b/Cmax. Lastly, an O(n log n) time heuristic is presented which generates a schedule with length at most 3/2 times that of an optimal schedule, for even number n 4, and 3/2 + 1/(2n) times that of an optimal schedule, for odd number n 4. These bounds are tight.