Two-Agent Single-Machine Scheduling with Linear Job-Dependent Position-Based Learning Effects
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
Recently, scheduling problems with position-dependent processing times have received considerable attention in the literature, where the processing times of jobs are dependent on the processing sequences. However, they did not consider cases in which each processed job has different learning or aging ratios. This means that the actual processing time for a job can be determined not only by the processing sequence, but also by the learning/aging ratio, which can reflect the degree of processing difficulties in subsequent jobs. Motivated by these remarks, in this paper, we consider a two-agent single-machine scheduling problem with linear job-dependent position-based learning effects, where two agents compete to use a common single machine and each job has a different learning ratio. Specifically, we take into account two different objective functions for two agents: one agent minimizes the total weighted completion time, and the other restricts the makespan to less than an upper bound. After formally defining the problem by developing a mixed integer non-linear programming formulation, we devise a branch-and-bound (B&B) algorithm to give optimal solutions by developing four dominance properties based on a pairwise interchange comparison and four properties regarding the feasibility of a considered sequence. We suggest a lower bound to speed up the search procedure in the B&B algorithm by fathoming any non-prominent nodes. As this problem is at least NP-hard, we suggest efficient genetic algorithms using different methods to generate the initial population and two crossover operations. Computational results show that the proposed algorithms are efficient to obtain near-optimal solutions.
Abstract
Recently, scheduling problems with position-dependent processing times have received considerable attention in the literature, where the processing times of jobs are dependent on the processing sequences. However, they did not consider cases in which each processed job has different learning or aging ratios. This means that the actual processing time for a job can be determined not only by the processing sequence, but also by the learning/aging ratio, which can reflect the degree of processing difficulties in subsequent jobs. Motivated by these remarks, in this paper, we consider a two-agent single-machine scheduling problem with linear job-dependent position-based learning effects, where two agents compete to use a common single machine and each job has a different learning ratio. Specifically, we take into account two different objective functions for two agents: one agent minimizes the total weighted completion time, and the other restricts the makespan to less than an upper bound. After formally defining the problem by developing a mixed integer non-linear programming formulation, we devise a branch-and-bound (B&B) algorithm to give optimal solutions by developing four dominance properties based on a pairwise interchange comparison and four properties regarding the feasibility of a considered sequence. We suggest a lower bound to speed up the search procedure in the B&B algorithm by fathoming any non-prominent nodes. As this problem is at least NP-hard, we suggest efficient genetic algorithms using different methods to generate the initial population and two crossover operations. Computational results show that the proposed algorithms are efficient to obtain near-optimal solutions.
참고문헌 (33)
- Agnetis, A., "Scheduling problems with two competing agents", Operations Research, 52(2), pp.229~242 (2004)
- Agnetis, A., "Multi-agent single machine scheduling", Annals of Operations Research, 150(1), pp.3~15 (2007)
- Bachman, A., "Scheduling jobs with position-dependent processing times", Journal of the Operational Research Society, 55, pp.257~264 (2004)
- Baker, K.R., "A multiple-criterion model for machine scheduling", Journal of Scheduling, 6(1), pp.7~16 (2003)
- Biskup D., "Single-machine scheduling with learning considerations", European Journal of Operational Research, 115(1), pp.173~178 (1999)
- Biskup, D., "A state-of-the-art review on scheduling with learning considerations", European Journal of Operational Research, 188(2), pp.315~329 (2008)
- Chang, P. C., "A note on due-date assignment and single machine scheduling with a learning and aging effect", International Journal of Production Economics, 117(1), pp.142~149 (2009)
- Cheng, T.C.E., "Single machine scheduling with learning effect considerations", Annals of Operations Research, 98(1), pp.273~290 (2000)
- Cheng, T. C. E., "Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs", Theoretical Computer Science, 362(1-3), pp.273~281 (2006)
- Cheng, T. C. E., "Two-agent scheduling with position-based deterioration jobs and learning effects", Applied Mathematics and Computation, 217(1), pp.8804~8824 (2011)
- Ding, G., "Single-machine scheduling problems with two agents competing for makespan", Life System Modeling and Intelligent Computing, 6328, pp.244~255 (2010)
- Graham, R. L., "Optimization and approximation in deterministic sequencing and scheduling theory : a survey", Annals of Discrete Mathematics, 5, pp.287~326 (1979)
- Hardy, G., "Inequalities" (1967), Cambridge University Press
- Hillier, F.S., "Introduction to Operations Research" (2015), McGraw Hill
- Knotts, G., "Agent-based project scheduling", IIE Transactions, 32(5), pp.387~401 (2000)
- Kuo, W.H., "Minimizing the makespan in a single-machine scheduling problem with the cyclic process of an aging effect", Journal of the Operational Research Society, 59, pp.416~420 (2008)
- Lee, W. C., "A single-machine scheduling problem with two-agent and deteriorating jobs", Applied Mathematical Modelling, 34(10), pp.3098~3107 (2010)
- Leung, J. Y. T., "Competitive two-agent scheduling and its applications", Operations Research, 58(2), pp.458~469 (2010)
- Li, D.C., "Solving a two-agent singlemachine scheduling problem considering learning effect", Computers and Operations Research, 39(7), pp.1644~1651 (2012)
- Liu, P., "Two-agent single-machine scheduling problems under increasing linear deterioration", Applied Mathematical Modelling, 35(5), pp.2290~2296 (2011)
- Liu, P., "Two-agent single-machine scheduling with position-dependent processing times", International Journal of Advanced Manufacturing Technology, 48(1), pp.325~331 (2010)
- Mitchell, M., "An introduction to genetic algorithm" (1996), MIT Press
- Mosheiov, G., "A note on scheduling deteriorating jobs", Mathematical and Computer Modelling, 41(8-9,), pp.883~886 (2005)
- Mosheiov, G., "Parallel machine scheduling with a learning effect", Journal of the Operational Research Society, 52(10), pp.1165~1169 (2001)
- Ng, C. T., "A note on the complexity of the problem of two-agent scheduling on a single machine", Journal of Combinatorial Optimization, 12(4), pp.387~394 (2006)
- Pessan, C., "An unrelated parallel machines model for an industrial production resetting problem", European Journal of Industrial Engineering, 2(2), pp.153~171 (2008)
- Wang, J., "Worst-case analysis for flow shop scheduling problems with an exponential learning effect", Journal of the Operational Research Society, 63, pp.130~137 (2012)
- Wang, J.B., "Flow-shop scheduling with a learning effect", Journal of the Operational Research Society, 56, pp.1325~1330 (2005)
- Wu, C. C., "Two-agent scheduling with learning consideration", Computers and Industrial Engineering, 61(4), pp.1324~1335 (2011)
- Wu, C. C., "Some single-machine scheduling problems with a truncation learning effect", Computers and Industrial Engineering, 60(4), pp.790~795 (2011)
- Wu, W. H., "A tabu method for a two-agent singlemachine scheduling with deterioration jobs", Computers and Operations Research, 40(8), pp.2116~2127 (2013)
- Yin, Y., "Two-agent single-machine scheduling with release times and deadlines", International Journal of Shipping and Transport Logistics, 5(1), pp.75~94 (2013)
- Yin, Y., "A generalization model of learning and deteriorating effects on a single-machine scheduling with past-sequence-dependent setup times", International Journal of Computer Integrated Manufacturing, 25(9), pp.804~813 (2012)