Equivalent time-dependent scheduling problems. (English) Zbl 1176.90213

Gawiejnowicz, Stanisław; Kurc, Wiesław; Pankowska, Lidia

Eur. J. Oper. Res. 196, No. 3, 919-929 (2009).

Summary: We introduce a general transformation of parallel-machine time-dependent scheduling problems with critical lines. Using the transformation we define the class of equivalent time-dependent scheduling problems. We show that given an initial parallel-machine time-dependent scheduling problem with linear job processing times and the total weighted starting time criterion, the problem can be transformed in a unique way into another problem of this type in such a way that both these problems are mutually dual. We prove that a schedule is optimal for the initial problem if and only if the schedule constructed by this transformation is optimal for the transformed problem. The presented results explain remarkable similarities between different time-dependent scheduling problems and simplify the proofs of properties of such problems.

MSC:

90B35

Deterministic scheduling theory in operations research

Keywords:

scheduling; deteriorating jobs; linear deterioration

References:

[1]	Alidaee, B.; Womer, N. K., Scheduling with time dependent processing times: Review and extensions, Journal of the Operational Research Society, 50, 711-720 (1999) · Zbl 1054.90542
[2]	Błażewicz, J.; Ecker, K. H.; Pesch, E.; Schmidt, G.; We¸glarz, J., Handbook on Scheduling (2007), Springer: Springer Berlin/Heidelberg
[3]	Chen, Z.-L., Parallel machine scheduling with time dependent processing times, Discrete Applied Mathematics, 70, 81-93 (1996), (Erratum: Discrete Applied Mathematics 75 (1996) 103) · Zbl 0855.68032
[4]	Cheng, T.-C. E.; Ding, Q., Single machine scheduling with deadlines and increasing rates of processing times, Acta Informatica, 36, 673-692 (2000) · Zbl 0958.68018
[5]	Cheng, T.-C. E.; Ding, Q., The complexity of scheduling starting time dependent tasks with release dates, Information Processing Letters, 65, 75-79 (1998) · Zbl 1338.68096
[6]	Cheng, T.-C. E.; Ding, Q.; Lin, B. M.-T., A concise survey of scheduling with time-dependent processing times, European Journal of Operational Research, 152, 1-13 (2004) · Zbl 1030.90023
[7]	Gawiejnowicz, S.; Kurc, W.; Pankowska, L., A greedy approach for a time-dependent scheduling problem, Lecture Notes in Computer Science, 2328, 79-86 (2002) · Zbl 1057.68547
[8]	Gawiejnowicz, S.; Kurc, W.; Pankowska, L., Analysis of a time-dependent scheduling problem by signatures of deterioration rate sequences, Discrete Applied Mathematics, 154, 2150-2166 (2006) · Zbl 1113.90059
[9]	Gawiejnowicz, S.; Kurc, W.; Pankowska, L., Minimizing time-dependent total completion time on parallel identical machines, Lecture Notes in Computer Science, 3019, 89-96 (2004) · Zbl 1128.68333
[10]	Gawiejnowicz, S.; Kurc, W.; Pankowska, L., Pareto and scalar bicriterion scheduling of deteriorating jobs, Computers and Operations Research, 33, 746-767 (2006) · Zbl 1116.90045
[11]	Gawiejnowicz, S.; Kurc, W.; Pankowska, L., Parallel machine scheduling of deteriorating jobs by steepest descent search, Lecture Notes in Computer Science, 3911, 116-123 (2006) · Zbl 1182.90042
[12]	Ho, K. I.-J.; Leung, J. Y.-T.; Wei, W.-D., Complexity of scheduling tasks with time-dependent execution times, Information Processing Letters, 48, 315-320 (1993) · Zbl 0942.68508
[13]	Jeng, A. A.-K.; Lin, B. M.-T., A note on parallel-machine scheduling with deteriorating jobs, Journal of the Operational Research Society, 58, 824-826 (2007) · Zbl 1177.90164
[14]	Kononov, A., Scheduling problems with linear increasing processing times, (Zimmermann, U.; etal., Operations Research 1996. Selected Papers of the Symposium on Operations Research (1997), Springer: Springer Berlin/Heidelberg), 208-212 · Zbl 0918.90085
[15]	Woeginger, G., When does a dynamic programming formulation guarantee the existence of an FPTAS?, INFORMS Journal on Computing, 12, 57-73 (2000) · Zbl 1034.90014