This note studies a unrelated parallel-machine scheduling problem with controllable processing times and job-dependent learning effects, where the objective function is to minimize the weighted sum of total completion time, total load, and total compression cost. We show that the problem can be solved in O(n$$) time, where m and n are the numbers of machines and jobs. We also show how to apply the technique to several single-machine scheduling problems with total criteria.
Keywords: Scheduling, unrelated parallel-machine, controllable processing times, learning effect
@article{RO_2021__55_2_561_0,
author = {Lin, Shan-Shan},
title = {A note on parallel-machine scheduling with controllable processing times and job-dependent learning effects},
journal = {RAIRO. Operations Research},
pages = {561--569},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {2},
doi = {10.1051/ro/2021030},
mrnumber = {4241821},
zbl = {1468.90051},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021030/}
}
TY - JOUR AU - Lin, Shan-Shan TI - A note on parallel-machine scheduling with controllable processing times and job-dependent learning effects JO - RAIRO. Operations Research PY - 2021 SP - 561 EP - 569 VL - 55 IS - 2 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021030/ DO - 10.1051/ro/2021030 LA - en ID - RO_2021__55_2_561_0 ER -
%0 Journal Article %A Lin, Shan-Shan %T A note on parallel-machine scheduling with controllable processing times and job-dependent learning effects %J RAIRO. Operations Research %D 2021 %P 561-569 %V 55 %N 2 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021030/ %R 10.1051/ro/2021030 %G en %F RO_2021__55_2_561_0
Lin, Shan-Shan. A note on parallel-machine scheduling with controllable processing times and job-dependent learning effects. RAIRO. Operations Research, Tome 55 (2021) no. 2, pp. 561-569. doi: 10.1051/ro/2021030
[1] and , Single machine scheduling with flow allowances. J. Oper. Res. Soc. 47 (1996) 1280–1285. | Zbl | DOI
[2] , , , and , Multiagent Scheduling: Models and Algorithms. Springer-Verlag, Berlin (2014). | MR | Zbl | DOI
[3] , and , Scheduling problems under learning effects: classification and cartography. Int. J. Prod. Res. 56 (2018) 1642–1661. | DOI
[4] , Simultaneous minimization of mean and variation of flow-time and waiting time in single machine systems. Oper. Res. 37 (1989) 118–125. | MR | Zbl | DOI
[5] , and , Due-date assignment and single machine scheduling with compressible processing times. Int. J. Prod. Econ. 43 (1996) 29–35. | DOI
[6] , A note on scheduling on a single processor with speed dependent on a number of executed jobs. Inf. Process. Lett. 57 (1996) 297–300. | MR | Zbl | DOI
[7] , Models and Algorithms of Time-Dependent Scheduling. Springer-Verlag, Berlin (2020). | MR | DOI
[8] and , A new approach to the maximum-flow problem. J. Assoc. Comput. Mach. 35 (1988) 921–940. | MR | Zbl | DOI
[9] , and , Sublinear-time parallel algorithms for matching and related problems. White Plains, New York, USA (1988) 174–185. | Zbl
[10] , , and , Using interior-point methods for fast parallel algorithms for bipartite matching and related problems. SIAM J. Comput. 21 (1992) 140–150. | MR | Zbl | DOI
[11] and , Some comments on sequencing with controllable processing times. Computing 68 (2002) 181–192. | MR | Zbl | DOI
[12] , Minimizing variation of flow time in single machine systems. Manage. Sci. 27 (1981) 1453–1459. | Zbl | DOI
[13] and , Single machine scheduling to minimise resource consumption cost with a bound on scheduling plus due date assignment penalties. Int. J. Prod. Res. 56 (2018) 3080–3096. | DOI
[14] , The Hungarian method for the assignment problem. Nav. Res. Logistics Q. 2 (1955) 83–97. | MR | Zbl | DOI
[15] , , and , Single-machine due-window assignment scheduling based on common flow allowance, learning effect and resource allocation. Int. J. Prod. Res. 53 (2015) 1228–1241. | DOI
[16] , , and , Scheduling jobs with simultaneous considerations of controllable processing times and learning effect. Neural Comput. App. 29 (2018) 1155–1162. | DOI
[17] , and , A single machine scheduling problem with common due window and controllable processing times. Ann. Oper. Res. 70 (1997) 145–154. | MR | Zbl | DOI
[18] , and , Common due window size and location determination in a single machine scheduling problem. J. Oper. Res. Soc. 49 (1998) 1007–1010. | Zbl | DOI
[19] , Due-window assignment and resource allocation scheduling with truncated learning effect and position-dependent weights. Discrete Dyn. Nat. Soc. 2020 (2020) 9260479. | MR | Zbl
[20] and , Due date assignment scheduling involving job-dependent learning effects and convex resource allocation. Eng. Optim. 52 (2020) 74–89. | MR | Zbl | DOI
[21] , and , Due-window assignment scheduling with resource processing times to minimise total resource consumption cost. Int. J. Prod. Res. 54 (2016) 1186–1195. | DOI
[22] , and , Scheduling jobs with truncated exponential sum-of-logarithm-processing-times based and position-based learning effects. Asia-Pac. J. Oper. Res. 32 (2015) 1550026. | MR | Zbl | DOI
[23] and , Job-dependent due-window assignment based on a common flow allowance. Found. Comput. Decis. Sci. 35 (2010) 185–195. | Zbl
[24] and , Scheduling with general job-dependent learning curves. Eur. J. Oper. Res. 147 (2003) 665–670. | MR | Zbl | DOI
[25] and , A survey of results for sequencing problems with controllable processing times. Discrete Appl. Math. 26 (1990) 271–287. | MR | Zbl | DOI
[26] and , Single-machine sequencing with controllable processing times. Eur. J. Oper. Res. 59 (1992) 298–302. | Zbl | DOI
[27] , and , Common due-date assignment to minimize total penalty for the one machine scheduling problem. Oper. Res. 30 (1982) 391–399. | Zbl | DOI
[28] , and , Optimal assignment of due dates for a single processor scheduling problem. Int. J. Prod. Res. 19 (1981) 393–399. | DOI
[29] and , A survey of scheduling with controllable processing times. Discrete Appl. Math. 155 (2007) 1643–1666. | MR | Zbl | DOI
[30] and , Scheduling with Time-Changing Effects and Rate-Modifying Activities. Springer-Verlag, Berlin (2017). | DOI
[31] , Optimizing batch-processing operations with batch-position-based learning effects. RAIRO:OR 55 (2020) S253–S269. | MR | Zbl | DOI
[32] , and , Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard. Inf. Process. Lett. 79 (2001) 273–280. | MR | Zbl | DOI
[33] , and , Single machine SLK/DIF due window assignment problem with learning effect and deteriorating jobs. Appl. Math. Modell. 37 (2013) 8394–8400. | MR | Zbl | DOI
[34] , , , and , Bicriterion scheduling with truncated learning effects and convex controllable processing times. Int. Trans. Oper. Res. 28 (2021) 1573–1593. | MR | Zbl | DOI
[35] and , Research on scheduling with job-dependent learning effect and convex resource dependent processing times. Int. J. Prod. Res. 53 (2015) 5826–5836. | DOI
[36] and , Single machine scheduling problems with controllable processing times and total absolute differences penalties. Eur. J. Oper. Res. 177 (2007) 638–645. | Zbl | DOI
[37] , and , Study on due-window assignment scheduling based on common flow allowance. Int. J. Prod. Econ. 165 (2015) 155–157. | DOI
[38] , and , Scheduling problems with multiple due windows assignment and controllable processing times on a single machine. Int. J. Prod. Econ. 150 (2014) 96–103. | DOI
[39] and , Single-machine scheduling with controllable processing times and learning effect. Int. J. Adv. Manuf. Technol. 54 (2011) 743–748. | DOI
[40] , Scheduling jobs on a single machine with release dates, delivery times and controllable processing times: worst-case analysis. Oper. Res. Lett. 10 (1991) 519–524. | MR | Zbl | DOI
Cité par Sources :
