Parallel Machines Scheduling with Rate-Modifying Activities and Total Absolute Differences Penalties

Yu-Bin Wu

Scheduling ； identical parallel machines ； rate-modifying activities ； polynomial algorithm

International Journal of Information and Management Sciences

25卷2期（2014 / 07 / 01）

407 - 418

英文

In this paper we consider identical parallel machines scheduling problems with rate-modifying activities. In this model, each machine has a rate-modifying activity that can change the processing rate of machine under consideration. Hence the actual processing times of jobs vary depending on whether the job is scheduled before or after the rate-modifying activity. We need to make a decision on when to schedule the rate-modifying activities and the sequence of jobs to minimize some objective function. We concentrate on two goals separately, namely, minimizing the total absolute differences in completion times (TADC) and the total absolute differences in waiting times (TADW). We show that the problems remain polynomially solvable under the proposed model.

1. Yang, S.-J.,Hsu, C.-J.,Yang, D.-L.(2010).Single-machine scheduling with due-date assignment and aging effect under a deteriorating maintenance activity consideration.International Journal of Information and Management Sciences,21,177-195.
   連結：
2. Alidaee, B.,Conlon, S.(1997).A note on the bicriterion scheduling problem involving total flowtime and range of lateness.International Journal of Information and Management Sciences,8,1-8.
3. Bagchi, U. B.(1989).Simultaneous minimization of mean and variation of flow-time and waiting time in single machine systems.Operations Research,37,118-125.
4. Chen, J.-S.,Yang, J.-S.(2007).Alternative models for solving single-machine scheduling with tool changes.International Journal of Information and Management Sciences,18,283-297.
5. Chen, W.-J.,Tsou, J.-C.(2008).Sequencing heuristic for scheduling jobs with periodic maintenance.International Journal of Information and Management Sciences,19,635-649.
6. Eilon, S.,Chowdhury, I. E.(1977).Minimizing waiting time variance in the single machine problem.Management Science,23,567-575.
7. Gordon, V. S.,Tarasevich, A. A.(2009).A note: Common due date assignment for a single machine scheduling with the rate-modifying activity.Computers & Operations Research,36,325-328.
8. Graham, R. L.,Lawler, E. L.,Lenstra, J. K.,Rinnooy Kan, A. H. G.(1979).Optimization and approximation in deterministic sequencing and scheduling: a survey.Annals of Discrete Mathematics,5,287-326.
9. Graves, G. H.,Lee, C.-Y.(1999).Scheduling maintenance and semiresumable jobs on a single machine.Naval Research Logistics,46,845-863.
10. Kanet, J. J.(1981).Minimizing variation of flow time in single machine systems.Management Science,27,1453-1459.
11. Lee, C.-Y.,Chen, Z.-L.(2000).Scheduling of jobs and maintenance activities on parallel machine.Naval Research Logistics,47,145-165.
12. Lee, C.-Y.,Leon, V. J.(2001).Machine scheduling with a rate-modifying activity.European Journal of Operational Research,128,119-128.
13. Lee, C.-Y.,Lin, C.-S.(2001).Single-machine scheduling with maintenance and repair rate-modifying activity.European Journal of Operational Research,135,493-513.
14. Merten, A. G.,Muller, M. E.(1972).Variance minimization in single machine sequencing problems.Management Science,18,518-528.
15. Mosheiov, G.(2008).Minimizing total absolute deviation of job completion times: extensions to position-dependent processing times and parallel identical machines.Journal of the Operational Research Society,59,1422-1424.
16. Mosheiov, G.(2001).Parallel machine scheduling with a learning effect.Journal of the Operational Research Society,52,1165-1169.
17. Mosheiov, G.,Oron, D.(2006).Due-date assignment and maintenance activity scheduling problem.Mathematical and Computer Modelling,44,1053-1057.
18. Mosheiov, G.,Sidney, J. B.(2004).New results on sequencing with rate modification.INFOR,41,155-163.
19. Murugesan, R.,Thamarai Selvi, S.,Alphonse Rajendran, P.,Sampath Kumar, V. S.(2003).Identification of a rank minimal optimal sequence for open shop scheduling problems.International Journal of Information and Management Sciences,14,37-55.
20. Pang, K.-C.(1995).Algorithmic analysis of the unrelated parallel machines scheduling problem to minmize mean weigted flowtime.International Journal of Information and Management Sciences,6,47-71.
21. Qi, X.,Chen, T.,Tu, F.(1999).Scheduling the maintenance on a single machines.Journal of Operational Research Society,50,1071-1078.
22. Schrage, L.(1975).Minimizing the time-in-system variance for a finite jobset.Management Science,21,540-543.
23. Vani, V.,Raghavachari, M.(1987).Deterministic and random single machine sequencing with variance minimization.Operations Research,35,111-120.
24. Wang, J.-B.,Wang M.-Z.(2012).Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time.Computers & Operations Research,39,492-497.
25. Wang, J.-B.,Wang M.-Z.(2012).Single-machine scheduling with nonlinear deterioration.Optimization Letters,6,87-98.
26. Wang, J.-B.,Wang M.-Z.(2011).Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects.Annals of Operations Research,191,155-169.
27. Wang, J.-B.,Wang, J.-J.,Ji, P.(2011).Scheduling jobs with chain precedence constraints and deteriorating jobs.Journal of the Operational Research Society,62,1765-1770.
28. Wang, J.-B.,Wei, C.-M.(2010).Parallel machine scheduling with a deteriorating maintenance activity and total absolute differences penalties.Applied Mathematics and Computation,217,8093-8099.
29. Wang, J.-B.,Xia, Z.-Q.(2007).Single machine scheduling problems with controllable processing times and total absolute differences penalties.European Journal of Operational Research,177,638-645.
30. Wang, J-B.(2010).Single-machine scheduling with a sum-of-actual-processing-time-based learning effect.Journal of the Operational Research Society,61,172-177.
31. Whitaker, L. O.(1996).College Station, TX.,Department of Industrial Engineering, Texas A&M University.
32. Yao, M.-J.,Huang, J.-Y.(2007).A global-optimization algorithm for solving the maintenance scheduling problem for a family of machines.International Journal of Information and Management Sciences,18,365-386.
33. Zhao, C.-L.,Tang, H.-Y.(2010).Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan.Applied Mathematical Modelling,34,837-841.
34. Zhao, C.-L.,Tang, H.-Y.,Cheng, C.-D.(2009).Two-parallel machines scheduling with rate-modifying activities to minimize total completion time.European Journal of Operational Research,198,354-357.