×

Flowshop scheduling with learning effect and job rejection. (English) Zbl 1456.90076

Summary: We study scheduling problems on a proportionate flowshop. Three objective functions are considered: minimum makespan, minimum total completion time, and minimum total load. We consider a learning process; thus, the processing time of a job processed later in sequence is reduced. The scheduler has the option of job rejection; i.e., only a subset of the jobs are processed and the rejected jobs are penalized. An upper bound on the total permitted rejection cost is assumed. Since the single-machine versions of these problems were shown to be NP-hard, we focus on the introduction of pseudopolynomial dynamic programming algorithms, indicating that the problems are NP-hard in the ordinary sense. We provide an extensive numerical study verifying that the proposed solution algorithms are very efficient and instances containing up to 80 jobs are solved in no more than 5 ms.

MSC:

90B35 Deterministic scheduling theory in operations research
90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agnetis, A.; Mosheiov, G., Scheduling with job-rejection and position-dependent processing times on proportionate flowshops, Optimization Letters, 11, 885-892 (2017) · Zbl 1369.90067 · doi:10.1007/s11590-016-1059-8
[2] Azzouz, A.; Ennigrou, M.; Ben Said, L., Scheduling problems under learning effects: Classification and cartography, International Journal of Production Research, 56, 1642-1661 (2018) · doi:10.1080/00207543.2017.1355576
[3] Biskup, D., Single-machine scheduling with learning considerations, European Journal of Operational Research, 115, 173-178 (1999) · Zbl 0946.90025 · doi:10.1016/S0377-2217(98)00246-X
[4] Biskup, D., A state-of-the-art review on scheduling with learning effects, European Journal of Operational Research, 188, 315-329 (2008) · Zbl 1129.90022 · doi:10.1016/j.ejor.2007.05.040
[5] Epstein, E.; Zebedat-Haider, H., Online scheduling of unit jobs on three machines with rejection: A tight result, Information Processing Letters, 116, 252-255 (2016) · Zbl 1348.90255 · doi:10.1016/j.ipl.2015.11.012
[6] Fiszman, S.; Mosheiov, G., Minimizing total load on a proportionate flowshop with position-dependent processing times and job rejection, Information Processing Letters, 132, 39-43 (2018) · Zbl 1410.90086 · doi:10.1016/j.ipl.2017.12.004
[7] Gawiejnowicz, S., A note on scheduling on a single processor with speed dependent on a number of executed jobs, Information Processing Letters, 57, 297-300 (1996) · Zbl 0875.68080 · doi:10.1016/0020-0190(96)00021-X
[8] Gawiejnowicz, S., Time-dependent scheduling (2008), Berlin: Springer, Berlin · Zbl 1155.90004 · doi:10.1007/978-3-540-69446-5_5
[9] Gerstl, E.; Mor, B.; Mosheiov, G., Minmax scheduling with acceptable lead-times: Extensions to position-dependent processing times, due-window and job rejection, Computers & Operations Research, 83, 150-156 (2017) · Zbl 1458.90295 · doi:10.1016/j.cor.2017.02.010
[10] Gerstl, E.; Mosheiov, G., Single machine scheduling problems with generalised due-dates and job-rejection, International Journal of Production Research, 55, 3164-3172 (2017) · doi:10.1080/00207543.2016.1266055
[11] Hill, CWL, International business: Competing in the global marketplace (2016), New York: McGraw-Hill, New York
[12] Mor, B.; Mosheiov, G., Minimizing maximum cost on a single machine with two competing agents and job rejection, Journal of the Operational Research Society, 67, 1524-1531 (2016) · doi:10.1057/s41274-016-0003-8
[13] Mor, B.; Mosheiov, G., A note: Minimizing total absolute deviation of job completion times on unrelated machines with general position-dependent processing times and job-rejection, Annals of Operations Research, 271, 1079-1085 (2018) · Zbl 1434.90064 · doi:10.1007/s10479-018-2779-1
[14] Mor, B.; Shapira, D., Improved algorithms for scheduling on proportionate flowshop with job-rejection, Journal of the Operational Research Society (2018) · doi:10.1080/01605682.2018.1506540
[15] Mor, B.; Shapira, D., Scheduling with regular performance measures and optional job rejection on a single machine, Journal of the Operational Research Society (2019) · doi:10.1080/01605682.2019.1621222
[16] Mosheiov, G., Scheduling problems with a learning effect, European Journal of Operational Research, 132, 687-693 (2001) · Zbl 1017.90051 · doi:10.1016/S0377-2217(00)00175-2
[17] Mosheiov, G.; Strusevich, V., Determining optimal sizes of bounded batches with rejection via quadratic min-cost flow, Naval Research Logistics, 64, 217-224 (2017) · Zbl 1411.90152 · doi:10.1002/nav.21740
[18] Ou, J.; Zhong, X.; Li, CL, Faster algorithms for single machine scheduling with release dates and rejection, Information Processing Letters, 116, 503-507 (2016) · Zbl 1335.68306 · doi:10.1016/j.ipl.2016.02.008
[19] Ou, J.; Zhong, X.; Wang, G., An improved heuristic for parallel machine scheduling with rejection, European Journal of Operational Research, 241, 653-661 (2015) · Zbl 1339.90148 · doi:10.1016/j.ejor.2014.09.028
[20] Shabtay, D.; Gaspar, N.; Kaspi, M., A survey on offline scheduling with rejection, Journal of Scheduling, 16, 3-28 (2013) · Zbl 1297.90058 · doi:10.1007/s10951-012-0303-z
[21] Shabtay, D.; Karhi, S.; Oron, D., Multipurpose scheduling with rejection and job processing times, Journal of Scheduling, 18, 75-88 (2015) · Zbl 1310.90055 · doi:10.1007/s10951-014-0386-9
[22] Thevenin, S.; Zufferey, N.; Widmer, M., Metaheuristics for a scheduling problem with rejection and tardiness penalties, Journal of Scheduling, 18, 89-105 (2015) · Zbl 1310.90056 · doi:10.1007/s10951-014-0395-8
[23] Zhang, L.; Lu, L.; Yuan, J., Single-machine scheduling under the job rejection constraint, Theoretical Computer Science, 411, 1877-1882 (2010) · Zbl 1192.68111 · doi:10.1016/j.tcs.2010.02.006
[24] Zhong, X.; Pan, Z.; Jiang, D., Scheduling with release times and rejection on two parallel machines, Journal of Combinatorial Optimization, 33, 934-944 (2017) · Zbl 1372.90056 · doi:10.1007/s10878-016-0016-x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.