Single machine batch scheduling with two non-disjoint agents and splitable jobs
- PDF / 452,425 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 6 Downloads / 181 Views
Single machine batch scheduling with two non-disjoint agents and splitable jobs Zhichao Geng1
· Jiayu Liu2
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We investigate the scheduling problem on a single bounded parallel-batch machine where jobs belong to two non-disjoint agents (called agent A and agent B) and are of equal length but different size. Each job’s size can be arbitrarily split into two parts and processed in the consecutive batches. It is permitted to process the jobs from different agents in a common batch. We show that it is unary NP-hard for the problem of minimizing the total weighted completion time of the jobs of agent A subject to the maximum cost of the jobs of agent B being upper bounded by a given threshold. For the case of the jobs of agent A having identical weights, we study the version of Pareto problem, and give a polynomial-time algorithm to generate all Pareto optimal points and a Pareto optimal schedule corresponding to each Pareto optimal point. Keywords Parallel-batch · Splitable jobs · Pareto optimal · Polynomial-time algorithm
1 Introduction Batch scheduling has attracted a great deal of research interest due to its extensive application in manufacturing industries, e.g., the burn-in operation of integrated circuit final testing at a semiconductor factory, the production of adhesives and glue, and the digital advertisement display business in E-commerce industry. The fundamental batch model introduced in Lee et al. (1992), called parallel-batch, means that a machine can process multiple jobs simultaneously as a batch, and the processing time of a batch is equal to the longest processing time of the jobs in the batch. Some extended models of the parallel-batch also have been provided in the literature, such as, the
B
Zhichao Geng [email protected]
1
School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, Henan, People’s Republic of China
2
Henan College of Transportation, Zhengzhou 450001, Henan, People’s Republic of China
123
Journal of Combinatorial Optimization
unbounded parallel-batch model (Brucker et al. 1998) for which a batch is capable of accommodating arbitrary number of jobs, and the so called mixed-batch model introduced in Wang et al. (2019) for which the processing time of a batch is equal to the weighted sum of the longest processing time and the total processing time of the jobs in the batch. As a subclass of the parallel-batch, the model studied in this paper is that, a batch can process multiple jobs with different sizes as long as the total size of jobs does not exceed the capacity of the batch machine, and the processing time of each batch is fixed and independent from the number of processed jobs. Such a subclass of parallelbatch is also called lot scheduling in Hou et al. (2014) and Zhang et al. (2019). This model derives from the real life applications of mass production of similar items, or the repetitive manufacturing of the same product, in the batch (or lot) mode in a factory with a limit
Data Loading...
