Single machine lot scheduling with non-uniform lot capacities and processing times
- PDF / 346,380 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 27 Downloads / 182 Views
Single machine lot scheduling with non-uniform lot capacities and processing times Ying Chen1 · Yongxi Cheng1,2 · Guiqing Zhang3 Accepted: 18 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper, we investigate the single machine lot scheduling problem in which each lot contains one or more jobs (or part of jobs). Jobs with different sizes are splittable and should be processed in consecutive lots. Any completed (part of a) job is delivered to the customer on its completion. We generalize the problem studied in Zhang et al. (Inf Process Lett 142:46–51, 2019) such that lots may have different capacities and processing times, and the sizes of jobs are unbounded. We show that for this generalized case, the WSPT (Weighted Shortest Processing Time first) rule is still optimal for both minimizing total weighted completion time and minimizing total weighted discounted completion time. Keywords Algorithms · Lot scheduling · Single machine · WSPT rule
1 Introduction In this paper we study a single machine lot scheduling problem in which multiple jobs (or part of jobs) with different sizes can be processed in one lot. The total size of jobs in any lot is not allowed to exceed the capacity of the lot, and lots may have different capacities and processing times. The processing time of each lot is fixed and independent from the number of processed jobs.
B
Guiqing Zhang [email protected] Ying Chen [email protected] Yongxi Cheng [email protected]
1
School of Management, Xi’an Jiaotong University, Xi’an 710049, China
2
State Key Lab for Manufacturing Systems Engineering, Xi’an 710049, China
3
School of Finance and Economics, Xi’an Jiaotong University, Xi’an 710049, China
123
Journal of Combinatorial Optimization
The lot scheduling problem has various applications including the burn-in operation of integrated circuit (IC) final testing at a semiconductor factory, glue production with a heating container to mix necessary raw materials, stone (or sand) wash processing of textile products such as jeans and denim jackets, etc. Lot scheduling also has application in digital advertisement (ad) display business in E-commerce industry, in which the capacity of a processing lot is the number of displayed webpages in a day for displaying customer ads (Zhang et al. 2019). For theoretical results on lot scheduling in literature, Hou et al. (2014) studied the single machine lot scheduling problem for the unweighted case, where the lots have the same capacity and processing time, and the size of each job is not larger than the capacity of one lot. The objective is to minimize the total completion time. They proved that the SPT (Shortest Processing Time first) rule optimally solves the problem. Zhang et al. (2019) generalized the lot scheduling problem studied by Hou et al. to the weighted case, and showed that the WSPT (Weighted Shortest Processing Time first) rule is optimal for both minimizing total weighted completion time and minimizing total weight
Data Loading...
