Two-Agent Single Machine Order Acceptance Scheduling Problem to Maximize Net Revenue

Complexity 2021:1-14 (2021)
  Copy   BIBTEX


The paper considers two-agent order acceptance scheduling problems with different scheduling criteria. Two agents have a set of jobs to be processed by a single machine. The processing time and due date of each job are known in advance. In the order accepting scheduling problem, jobs are allowed to be rejected. The objective of the problem is to maximize the net revenue while keeping the weighted number of tardy jobs for the second agent within a predetermined value. A mixed-integer linear programming formulation is provided to obtain the optimal solution. The problem is considered as an NP-hard problem. Therefore, MILP can be used to solve small problem instances optimally. To solve the problem instances with realistic size, heuristic and metaheuristic algorithms have been proposed. A heuristic method is used to determine and secure a quick solution while the metaheuristic based on particle swarm optimization is designed to obtain the near-optimal solution. A numerical experiment is piloted and conducted on the benchmark instances that could be obtained from the literature. The performances of the proposed algorithms are tested through numerical experiments. The proposed PSO can obtain the solution within 0.1% of the optimal solution for problem instances up to 60 jobs. The performance of the proposed PSO is found to be significantly better than the performance of the heuristic.



    Upload a copy of this work     Papers currently archived: 89,654

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles


Added to PP

5 (#1,331,088)

6 months
1 (#1,014,737)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

Yuanyuan Liu
University of Tennessee, Knoxville

Citations of this work

No citations found.

Add more citations