Scheduling problems have been studied for many years for optimizing resource allocation as scheduling plays a critical role in many manufacturing and service industries. During last two decades, two-agent scheduling problems have been used in many systems, such as railroad allocation system, aircraft landing system and so on. This thesis considers various two-agent scheduling problems with a single machine, which is responsible for processing jobs from two agents. The research of single machine with two-agent scheduling models can be classified into two main categories: minimality model and feasibility model. The feasibility model based two-agent scheduling problems are studied in this thesis. In a feasibility model, the scheduling problem is objective to minimize the objective function of one agent while keeping the objective function of the other agent within a pre-specified level. In the present thesis, mathematical models, heuristics, and Ant Colony Optimization based meta-heuristics are proposed for solving the problems studied in this thesis. Furthermore, this thesis also provides a detailed and systemic survey (literature review) of the two-agent scheduling problem literature on models with a given due date. In the chapter of survey of two-agent scheduling problems with due date, the computational complexity and proposed algorithms for the due-date-related two-agent scheduling problems are list. The two-agent scheduling problems studied and proposed algorithms in this thesis are extremely useful for improving the productivity and efficiency of the manufacturing environment in a supply chain system.