The problem of scheduling with multi agent has been studiedfor more than one decade and significant advances have been madeover the years. However, most work has paid more attention to the conditionthat machines are available during planning horizon. Motivatedby the observations, this paper studies a two-agent scheduling modelwith multiple availability constraint. Each agent aims at minimizing afunction which depends only on the completion times of its jobs. Theproblem is to find a schedule that minimizes the objective function ofone agent, subject to the objective function of the other agent does notexceed a given threshold Q. some new dominance properties for thisproblem percent and next, using these properties, we develop a geneticalgorithm with modified crossover for the problem. Computational resultsare also presented to determine the performance of the proposedgenetic algorithms. Manuscript profile