In this paper, We deal with the scheduling problems with simple linear deterioration function on unrelated parallel-machine and identical parallel-machine. We assume that all the jobs (tasks) are available at time zero, but all machines (processors) may not be available simultaneously at time zero. The objective functions are to minimize the total logarithm of completion time, the total logarithm of machine load, the total absolute differences in logarithm completion times and the total absolute differences in logarithm waiting times respectively. We provide the polynomial-time algorithms to solve the problems under the proposed model respectively.

Keywords:

References

1. Bagchi, UB (1989). Simultaneous minimization of mean and variation of flow-time and waiting time in single machine systems. Operations Research, 37, 118–125. Crossref, Web of Science, Google Scholar
2. Bock, S, D Briskorn and A Horbach (2012). Scheduling flexible maintenance activities subject to job-dependent machine deterioration. Journal of Scheduling, 15, 565–578. Crossref, Web of Science, Google Scholar
3. Chen, Z-L (1996). Parallel machine scheduling with time dependent processing times. Discrete Applied Mathematics, Vol. 70, pp. 81–93, 1996 [Erratum, Discrete Applied Mathematics, 75, 103, 1996]. Crossref, Web of Science, Google Scholar
4. Cheng, TCE, C-J Hsu, Y-C Huang and W-C Lee (2011). Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness. Computers & Operations Research, 38, 1760–1765. Crossref, Web of Science, Google Scholar
5. Cheng, M, PR Tadikamalla, J Shang and S Zhang (2014). Bicriteria hierarchical optimization of two-machine flow shop scheduling problem with time-dependent deteriorating jobs. European Journal of Operational Research, 234, 650–657. Crossref, Web of Science, Google Scholar
6. Cheng, M, G Wang and L He (2009). Parallel machines scheduling problems with proportionally deteriorating jobs, International Journal of Systems Science, 40, 53–57. Crossref, Web of Science, Google Scholar
7. Gawiejnowicz, S (2008). Time-Dependent Scheduling. Berlin: Springer. Crossref, Google Scholar
8. Graham, RL and EL Lawler, JK Lenstra and AHG Rinnooy Kan (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326. Crossref, Google Scholar
9. Hardy, GH, JE Littlewood and G Polya (1967). Inequalities. Cambridge: Cambridge University Press. Google Scholar
10. Huang, X, M-Z Wang and P Ji (2014). Parallel machines scheduling with deteriorating and learning effects. Optimization Letters, 8, 493–500. Crossref, Web of Science, Google Scholar
11. Ji, M and TCE Cheng (2008). Parallel-machine scheduling with simple linear deterioration to minimize total completion time. European Journal of Operational Research, 188, 342–347. Crossref, Web of Science, Google Scholar
12. Ji, M and TCE Cheng (2010). Scheduling with job dependent learning effects and multiple rate-modifying activities. Information Processing Letters, 110, 460–463. Crossref, Web of Science, Google Scholar
13. Kanet, JJ (1981). Minimizing variation of flow time in single machine systems. Management Science, 27, 1453–1459. Crossref, Web of Science, Google Scholar
14. Kononov, A (1997). Scheduling problems with linear increasing processing times. Operations Research Proceedings, Berlin: Springer, 199–206. Google Scholar
15. Kuo, W-H and D-L Yang (2008). Parallel-machine scheduling with time dependent processing times. Theoretical Computer Science, 393, 204–210. Crossref, Web of Science, Google Scholar
16. Lee, C-Y (1991). Parallel machines scheduling with nonsimultaneous machine available time. Discrete Applied Mathematics, 30, 53–61. Crossref, Web of Science, Google Scholar
17. Lee, W-C and Z-S Lu (2012). Group scheduling with deteriorating jobs to minimize the total weighted number of late jobs. Applied Mathematics and Computation, 218, 8750–8757. Crossref, Web of Science, Google Scholar
18. Li, X-J, J-J Wang and X-R Wang (2015). Single-machine scheduling with learning effect, deteriorating jobs and convex resource dependent processing times. Asia-Pacific Journal of Operational Research, 32(3), 1550033. Link, Web of Science, Google Scholar
19. Lu, Y-Y, J-J Wang and J-B Wang (2014). Single machine group scheduling with decreasing time-dependent processing times subject to release dates. Applied Mathematics and Computation, 234, 286–292. Crossref, Web of Science, Google Scholar
20. Mazdeh, MM, F Zaerpour, A Zareei and A. Hajinezhad (2010). Parallel machines scheduling to minimize job tardiness and machine deteriorating cost with deteriorating jobs. Applied Mathematical Modelling, 34, 1498–1510. Crossref, Web of Science, Google Scholar
21. Mor, B and G Mosheiov (2011). Total absolute deviation of job completion times on uniform and unrelated machines. Computers and Operations Research, 38, 660–665. Crossref, Web of Science, Google Scholar
22. Mosheiov, G (1994). Scheduling job under simple linear deterioration. Computers and Operations Research, 21, 653–659. Crossref, Web of Science, Google Scholar
23. Mosheiov, G. (2001). Parallel machine scheduling with a learning effect. Journal of the Operational Research Society, 52, 1165–1169. Crossref, Web of Science, Google Scholar
24. Pinedo M (2012). Scheduling: Theory, Algorithms and Systems, 4th edn. New York: Springer. Crossref, Google Scholar
25. Rudek, R, A Rudek and A Kozik (2013). The solution algorithms for the multiprocessor scheduling with workspan criterion. Expert Systems with Applications, 40, 2799–2806. Crossref, Web of Science, Google Scholar
26. Shen, L, D Wang and X-Y Wang (2013). Parallel-machine scheduling with non-simultaneous machine available time. Applied Mathematical Modelling, 37, 5227–5232. Crossref, Web of Science, Google Scholar
27. Stirzaker D (1995). Elementary Probability. Cambridge: Cambridge University Press. Google Scholar
28. Wang, J-B, X Huang, Y-B Wu and P Ji (2012a). Group scheduling with independent setup times, ready times, and deteriorating job processing times. International Journal of Advanced Manufacturing Technology, 60, 643–649. Crossref, Web of Science, Google Scholar
29. Wang, J-B, P Ji, TCE Cheng and D Wang (2012b). Minimizing makespan in a two-machine flow shop with effects of deterioration and learning. Optimization Letters, 6, 1393–1409. Crossref, Web of Science, Google Scholar
30. Wang, J-B and M-Z Wang (2013a). Minimizing makespan in three-machine flow shops with deteriorating jobs. Computers & Operations Research, 40, 547–557. Crossref, Web of Science, Google Scholar
31. Wang, J-B and M-Z Wang (2013b). Makespan minimization on three-machine flow shop with deteriorating jobs. Asia-Pacific Journal of Operational Research, 30(6), 1350022. Link, Web of Science, Google Scholar
32. Wang, J-B and J-J Wang (2014a). Single machine group scheduling with time dependent processing times and ready times. Information Sciences, 275, 226–231. Crossref, Web of Science, Google Scholar
33. Wang, J-B and J-J Wang (2015). Single-machine scheduling problems with precedence constraints and simple linear deterioration. Applied Mathematical Modelling, 39, 1172–1182. Crossref, Web of Science, Google Scholar
34. Wang, X-Y, Z Zhou, P Ji and J-B Wang (2014). Parallel machines scheduling with simple linear job deterioration and non-simultaneous machine available times. Computers & Industrial Engineering, 74, 88–91. Crossref, Web of Science, Google Scholar
35. Zhang, M and C Luo (2013). Parallel-machine scheduling with deteriorating jobs, rejection and a fixed non-availability interval. Applied Mathematics and Computation, 224, 405–411. Crossref, Web of Science, Google Scholar