Serial-batching scheduling with two agents to minimize makespan and maximum cost
- PDF / 327,331 Bytes
- 9 Pages / 595.276 x 790.866 pts Page_size
- 28 Downloads / 173 Views
Serial-batching scheduling with two agents to minimize makespan and maximum cost Cheng He1 · Chunqi Xu2 · Hao Lin1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This paper considers three serial-batching scheduling problems with two agents to minimize the makespan of agent A and maximum cost (or maximum lateness) of agent B simultaneously. In these two-agent scheduling problems, jobs of different agents cannot be processed in a common batch, and the cost function of an agent depends only on its jobs. For each problem, we present a polynomial-time algorithm which can find all Pareto optimal solutions. Keywords Two-agent scheduling · Serial-batching · Makespan · Maximum cost · Maximum lateness
1 Introduction Each agent has a job set and has an objective function that relies on the completion times of his/her own jobs. The jobs of different agents cannot be scheduled in the same batch. A serial-batching machine can simultaneously process up to b jobs in a batch, where b is the capacity of a batch. Regarding capacity b, the unbounded model (b ≥ n) and the bounded model (b < n) are considered in the paper, where n is the number of jobs. The processing time of a batch is equal to the sum of processing times of all jobs in the batch. Moreover, when a new batch starts, a constant setup time s is inserted. The goals of the problems are to minimize the A of agent A and the maximum cost f B (or makespan Cmax max B ) of agent B simultaneously, i.e., to maximum lateness L max find all Pareto optimal schedules for the two criteria. Here, two objective functions may represent different interests of two decision-makers. Actually, it is worthwhile to study a variety of problems combining multiple criteria and batching aspects. In this paper, we work with three cases. This work was supported by Key Research Project of Henan Higher Education Institutions (20A110003) and Science and Technology Activities Project for Henan Overseas Students.
B
Cheng He [email protected]
1
School of Science, Henan University of Technology, Zhengzhou 450001, Henan, China
2
School of Economic and Management, China University of Geosciences (Beijing), Beijing 100083, China
The problems described above may be found in various manufacturing applications and many negotiation procedures. For example, a factory may process orders from two types of customers. The customer orders are interpreted as jobs to be executed. Customer A hopes that the completion time of his last processed job will be as early as possible, while each job from customer B has a cost, and customer B hopes that the maximum cost of his jobs will be as small as possible. On the other hand, the manufacturer is also concerned with minimizing any order delays, which cause financial loss. In order to meet the needs of two customers to the greatest extent possible, the manufacturer needs to devise certain mechanisms to encourage the agents to cooperate. This situation can be modeled as the simultaneous optimization problem under consideration. The concept of
Data Loading...
