Scheduling with Multiple Common Due Windows Assignment and General Position-Dependent and Resource-Dependent Processing Times

10.6186/IJIMS.2014.25.2.2

Suh-Jenq Yang；Chien-Jung Lai

Scheduling ； multiple common due windows assignment ； position-dependent processing time ； resource-dependent processing time

International Journal of Information and Management Sciences

25卷2期（2014 / 07 / 01）

101 - 120

英文

In this paper we consider multiple common due windows assignment and single-machine scheduling problems with general position-dependent and resource-dependent processing times simultaneously. Multiple common due windows, an extension of single common due window, allow a job to fit one from multiple common due windows. We assume that the number of common due windows to be assigned to the jobs is given. Two resource allocation models are examined, namely the linear resource consumption model and the convex re-source consumption model. The actual processing time of a job is a function of its scheduled position in a sequence and its resource allocation. We aim to determine jointly the optimal common due window positions and sizes, the set of jobs assigned to each common due window, the optimal resource allocations, and the optimal schedule for minimizing an objective function which includes earliness, tardiness, common due windows assignment, makespan, and resource consumption costs. We provide some properties of the optimal schedule for the problem and propose polynomial time algorithms for all the problems considered.

1. Yang, S. J.(2012).Scheduling common/slack due date assignment with simultaneous considerations of time-dependent and position-dependent deterioration effects and deteriorating maintenance on a single machine.International Journal of Information and Management Sciences,23,257-272.
   連結：
2. 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.
   連結：
3. Bachman, A.,Janiak, A.(2004).Scheduling jobs with position-dependent processing times.Journal of the Operational Research Society,55,257-264.
4. Biskup, D.(2008).A state-of-the-art review on scheduling with learning effects.European Journal of Operational Research,188,315-329.
5. Chen, Z. L.,Lee, C. Y.(2002).Parallel machine scheduling with a common due window.European Journal of Operational Research,136,512-527.
6. Cheng, T. C. E.,Oğaz, C.,Qi, X. D.(1996).Due-date assignment and single machine scheduling with compressible processing times.International Journal of Production Economics,43,29-35.
7. Gordon, V. S.,Proth, J. M.,Chu, C.(2002).A survey of the state-of-art of common due date assignment and scheduling research.European Journal of Operational Research,139,1-25.
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. Hardy, G. H.,Littlewood, J. E.,Polya, G.(1967).Inequalities.London:Cambridge University Press.
10. Hsu, C. J.,Yang, S. J.,Yang, D. L.(2011).Two due date assignment problems with position-dependent processing time on a single-machine.Computers & Industrial Engineering,60,796-800.
11. Janiak, A.(Ed.)(2006).Scheduling in Computer and Manufacturing Systems.Warszawa, Poland:WKL.
12. Janiak, A.,Rudek, R.(2009).Experience based approach to scheduling problems with the learning effect.IEEE Transactions on Systems, Man, and Cybernetics-Part A,39,344-357.
13. Jozefowska, J.(2007).Just-in-Time Scheduling: Models and Algorithms for Computer and Manufacturing Systems.New York:Springer-Verlag Inc..
14. Kuo, W. H.,Yang, D. L.(2008).A note on due-date assignment and single-machine scheduling with deteriorating jobs.Journal of the Operational Research Society,59,857-859.
15. Leung, J. Y.(Ed.)(2004).Handbook of Scheduling: Algorithms, Models and Performance Analysis.Boca Raton, FL.:CRC Press.
16. Liman, S. D.,Panwalkar, S. S.,Thongmee, S.(1997).A single machine scheduling problem with common due window and controllable processing times.Annals of Operations Research,70,145-154.
17. Liman, S. D.,Panwalkar, S. S.,Thongmee, S.(1998).Common due window size and location determination in a single machine scheduling problem.Journal of the Operational Research Society,49,1007-1010.
18. Liman, S. D.,Panwalkar, S. S.,Thongmee, S.(1996).Determination of common due window location in a single machine scheduling problem.European Journal of Operational Research,93,68-74.
19. Mor, B.,Mosheiov, G.(2012).Scheduling a maintenance activity and due-window assignment based on common flow allowance.International Journal of Production Economics,135,222-230.
20. Mosheiov, G.,Sarig, A.(2009).Scheduling a maintenance activity and due-window assignment on a single machine.Computers & Operations Research,36,2541-2545.
21. Mosheiov, G.,Sarig, A.(2008).A due-window assignment problem with position-dependent processing times.Journal of the Operational Research Society,59,997-1003.
22. Panwalkar, S. S.,Rajagopalan, R.(1992).Single-machine sequencing with controllable processing times.European Journal of Operational Research,59,298-302.
23. Shabtay, D.,Steiner, G.(2007).A survey of scheduling with controllable processing times.Discrete Applied Mathematics,155,1643-1666.
24. Shabtay, D.,Steiner, G.(2008).The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times.Annals of Operations Research,159,25-40.
25. Sidney, J.(1977).Optimal single-machine scheduling with earliness and tardiness penalties.Operations Research,25,62-69.
26. Van Wassenhove, L. N.,Baker, K. R.(1982).A bicriterion approach to time/cost trade-offs in sequencing.European Journal of Operational Research,11,48-52.
27. Vickson, R. G.(1980).Choosing the job sequence and processing times to minimize processing plus flow cost on a single machine.Operations Research,28,1155-1167.
28. Vickson, R. G.(1980).Two single-machine sequencing problems involving controllable job processing times.AIIE Transactions,12,258-262.
29. Wan, G.(2007).Single machine common due window scheduling with controllable job processing times.Lecture Notes in Computer Science,4616,279-290.
30. Wang, J. B.,Wang, M. Z.(2010).Single machine multiple common due dates scheduling with learning effects.Computers & Mathematics with Applications,60,2998-3002.
31. Yang, D. L.,Lai, C. J.,Yang, S. J.(2014).Scheduling problems with multiple due windows assignment and controllable processing times on a single machine.International Journal of Production Economics,150,96-103.
32. Yang, S. J.,Lee, H. T.,Guo, J. Y.(2013).Multiple common due dates assignment and scheduling problems with resource allocation and general position-dependent deterioration effect.International Journal of Advanced Manufacturing Technology,67,181-188.
33. Yang, S. J.,Yang, D. L.(2010).Minimizing the total completion time in single-machine scheduling with aging/deteriorating effects and deteriorating maintenance activities.Computers & Mathematics with Applications,60,2161-2169.
34. Yang, W. H.(2009).Sequencing jobs subject to multiple common due dates.The 10th Asia Pacific Industrial Engineering & Management Systems Conference
35. Yin, Y.,Cheng, T. C. E.,Hsu, C. J.,Wu, C. C.(2013).Single-machine batch delivery scheduling with an assignable common due window.Omega,41,216-225.
36. Yin, Y.,Cheng, T. C. E.,Wu, C. C.,Cheng, S. R.(2014).Single-machine due window assignment and scheduling with a common allowance and controllable job processing time.Journal of the Operational Research Society,65,1-13.
37. Yin, Y.,Cheng, T. C. E.,Wu, C. C.,Cheng, S. R.(2013).Single-machine common due-date scheduling with batch delivery costs and resource-dependent processing times.International Journal of Production Research,51,5083-5099.
38. Yin, Y.,Cheng, T. C. E.,Xu, D. andWu, C. C.(2012).Common due date assignment and scheduling with a rate-modifying activity to minimize the due date, earliness, tardiness, holding, and batch delivery cost.Computers & Industrial Engineering,63,223-234.

1. 清水悠揮(2017)。在Halide中運用機器學習方法來進行異質計算。國立臺灣大學資訊工程學系學位論文。2017。1-41。