×

Scheduling jobs with processing times dependent on position, starting time, and allotted resource. (English) Zbl 1251.90198

Summary: We consider single-machine scheduling problem in which the processing time of a job is a function of its position in a sequence, its starting time, and its resource allocation. The objective is to find the optimal sequence of jobs and the optimal resource allocation separately. We concentrate on two goals separately, namely, minimizing a cost function containing makespan, total completion time, total absolute differences in completion times, and total resource cost; minimizing a cost function containing makespan, total waiting time, total absolute differences in waiting times, and total resource cost. The problem is modeled as an assignment problem, and thus can be solved in polynomial time. Some extensions of the problem are also shown.

MSC:

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

References:

[1] DOI: 10.1057/jors.1996.155 · Zbl 0863.90079 · doi:10.1057/jors.1996.155
[2] DOI: 10.1057/palgrave.jors.2600740 · Zbl 1054.90542 · doi:10.1057/palgrave.jors.2600740
[3] DOI: 10.1057/palgrave.jors.2601689 · Zbl 1095.90033 · doi:10.1057/palgrave.jors.2601689
[4] DOI: 10.1016/S0020-0190(01)00196-X · Zbl 1032.68019 · doi:10.1016/S0020-0190(01)00196-X
[5] DOI: 10.1287/opre.37.1.118 · Zbl 0661.90046 · doi:10.1287/opre.37.1.118
[6] DOI: 10.1016/S0377-2217(98)00246-X · Zbl 0946.90025 · doi:10.1016/S0377-2217(98)00246-X
[7] DOI: 10.1016/j.ejor.2007.05.040 · Zbl 1129.90022 · doi:10.1016/j.ejor.2007.05.040
[8] DOI: 10.1109/9.293187 · Zbl 0816.90080 · doi:10.1109/9.293187
[9] DOI: 10.1023/A:1018943300630 · Zbl 0997.90035 · doi:10.1023/A:1018943300630
[10] DOI: 10.1137/S1052623495288192 · Zbl 0907.68113 · doi:10.1137/S1052623495288192
[11] DOI: 10.1016/S0377-2217(02)00909-8 · Zbl 1030.90023 · doi:10.1016/S0377-2217(02)00909-8
[12] Gawiejnowicz S., Time-Dependent Scheduling (2008) · Zbl 1155.90004
[13] DOI: 10.1016/j.ejor.2009.07.021 · Zbl 1176.90216 · doi:10.1016/j.ejor.2009.07.021
[14] DOI: 10.1007/s10951-008-0064-x · Zbl 1168.90441 · doi:10.1007/s10951-008-0064-x
[15] DOI: 10.1016/S0167-5060(08)70356-X · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[16] DOI: 10.1016/j.cor.2004.11.009 · Zbl 1087.90008 · doi:10.1016/j.cor.2004.11.009
[17] DOI: 10.1002/(SICI)1520-6750(199802)45:1<99::AID-NAV6>3.0.CO;2-G · Zbl 0897.90127 · doi:10.1002/(SICI)1520-6750(199802)45:1<99::AID-NAV6>3.0.CO;2-G
[18] DOI: 10.1016/0377-2217(96)00129-4 · Zbl 0947.90584 · doi:10.1016/0377-2217(96)00129-4
[19] DOI: 10.1287/mnsc.27.12.1453 · Zbl 0473.90048 · doi:10.1287/mnsc.27.12.1453
[20] Kovalyov M. Y., Informatica 17 pp 13–
[21] DOI: 10.1023/A:1009626427432 · Zbl 0903.90100 · doi:10.1023/A:1009626427432
[22] DOI: 10.1016/j.cie.2007.10.010 · doi:10.1016/j.cie.2007.10.010
[23] Lee W.-C., Computers & Industrial Engineering 36 pp 2111–
[24] DOI: 10.1016/j.ejor.2010.02.026 · Zbl 1188.90099 · doi:10.1016/j.ejor.2010.02.026
[25] DOI: 10.1057/palgrave.jors.2600601 · Zbl 1140.90405 · doi:10.1057/palgrave.jors.2600601
[26] DOI: 10.1016/j.ijpe.2008.11.011 · doi:10.1016/j.ijpe.2008.11.011
[27] DOI: 10.1016/0305-0548(94)90080-9 · Zbl 0810.90074 · doi:10.1016/0305-0548(94)90080-9
[28] DOI: 10.1016/0166-218X(90)90105-L · Zbl 0693.90056 · doi:10.1016/0166-218X(90)90105-L
[29] DOI: 10.1016/0377-2217(92)90144-X · Zbl 0760.90058 · doi:10.1016/0377-2217(92)90144-X
[30] DOI: 10.1287/opre.30.2.391 · Zbl 0481.90042 · doi:10.1287/opre.30.2.391
[31] Pinedo M., Scheduling: Theory, Algorithms, and Systems (2002) · Zbl 1145.90394
[32] DOI: 10.1080/00207548108956667 · doi:10.1080/00207548108956667
[33] DOI: 10.1016/j.dam.2007.02.003 · Zbl 1119.90022 · doi:10.1016/j.dam.2007.02.003
[34] DOI: 10.1287/msom.1060.0139 · doi:10.1287/msom.1060.0139
[35] DOI: 10.1007/s10479-007-0269-y · Zbl 1151.90432 · doi:10.1007/s10479-007-0269-y
[36] DOI: 10.1016/j.apm.2009.01.004 · Zbl 1205.90137 · doi:10.1016/j.apm.2009.01.004
[37] DOI: 10.1016/j.cor.2006.12.026 · Zbl 1180.90143 · doi:10.1016/j.cor.2006.12.026
[38] DOI: 10.1016/j.cie.2010.06.002 · doi:10.1016/j.cie.2010.06.002
[39] DOI: 10.1016/j.cie.2008.10.002 · doi:10.1016/j.cie.2008.10.002
[40] DOI: 10.1016/j.cie.2010.05.014 · doi:10.1016/j.cie.2010.05.014
[41] DOI: 10.1016/j.cie.2009.06.016 · doi:10.1016/j.cie.2009.06.016
[42] DOI: 10.1016/j.cie.2010.02.006 · doi:10.1016/j.cie.2010.02.006
[43] Zhang X., Applied Mathematics and Computation 216 pp 1259–
[44] DOI: 10.1016/j.cie.2009.08.006 · doi:10.1016/j.cie.2009.08.006
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.