Multitasking scheduling with batch distribution and due date assignment
- PDF / 359,350 Bytes
- 12 Pages / 595.276 x 790.866 pts Page_size
- 13 Downloads / 199 Views
ORIGINAL ARTICLE
Multitasking scheduling with batch distribution and due date assignment Xinrui Xu1 · Guangqiang Yin2 · Chunyu Wang2 Received: 2 June 2020 / Accepted: 25 July 2020 © The Author(s) 2020
Abstract This study addresses the multitasking scheduling problems with batch distribution and due date assignment (DDA). Compared with classical scheduling problems with due date-related optimization functions, the job due dates are decision variables rather than given parameters. The jobs completed are distributed in batches, and the sizes of all batches are identical, which may be bounded or unbounded. The jobs in every batch are scheduled one by one. Each batch incurs a fixed cost. Under multitasking environment, it allows the machine to put an uncompleted job on hold and turn to another uncompleted job. The goal is to identify the optimal primary job sequence, the optimal job due dates, and the optimal batch production and distribution strategy so that one of the following two optimization functions is minimised: the total cost composed of the earliness penalty, DDA cost, tardiness penalty and batch distribution cost, and the total cost composed of the earliness penalty, weighted number of late jobs, DDA cost and batch distribution cost. We devise efficient exact algorithms for the problems we consider, and perform numerical experiments to check how multitasking affects the scheduling cost or value, the results of which can assist decision-makers to justify the extent to put to use or refrain from multitasking. Keywords Multitasking · Scheduling · Due date assignment · Batch distribution
Introduction The problem we investigate in this study covers three momentous sub-areas of scheduling research, i.e., multitasking scheduling, scheduling with DDA, and batch distribution scheduling. All of these three sub-areas have been widely investigated in the literature. In the remaining part of this section, we briefly review some related research from these sub-areas. The research about multitasking scheduling is initialized by Hall et al. [12], where the processing of a chosen job can be suspended by other uncompleted jobs. The authors demonstrate that the solution algorithms for some classical scheduling criteria are more complex in terms of time complexity than the corresponding problems without multi-
B
Chunyu Wang [email protected]
1
School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 610054, China
2
School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu 610054, China
tasking, and verify the effects of multitasking on the schedule criteria through computational experiments. Subsequently, the research on this line has attracted increasing attention. Hall et al. [13] introduce two different multitasking scheduling problems, in which the first one addresses alternate period processing and the second one investigates shared processing. Ji et al. [15] consider the identical parallel-machine schedulin
Data Loading...
