A tabu method for a two-agent single-machine scheduling with deterioration jobs. (English) Zbl 1348.90326
Summary: In recent 10 years, the multi-agent idea applied in scheduling issues has received continuing attention. However, the study of the multi-agent scheduling with deteriorating jobs is relatively limited. In light of this, this paper deliberates upon a two-agent single-machine scheduling problem with deteriorating jobs. Taking the proposed model, the actual processing time of a job from both the first agent and the second agent is modeled as a linearly increasing function of its starting time. The goal of this paper is to minimize the total weighted number of tardy jobs of the first agent subject to the condition that the maximum lateness of the second agent is allowed to have an upper bound. The complexity of the model concerned in the paper is claimed as an NP-hard one. Following that, several dominance rules and a lower bound are proposed to be applied in a branch-and-bound algorithm for the optimal solution, and a tabu algorithm is applied to find near-optimal solutions for the problem. The simulation results obtained from all the proposed algorithms are also reported.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
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] | Agnetis, A.; Mirchandani, P. B.; Pacciarelli, D.; Pacifici, A., Scheduling problems with two competing agents, Operations Research, 52, 229-242 (2004) · Zbl 1165.90446 |
| [3] | Agnetis, A.; Pacciarelli, D.; Pacifici, A., Multi-agent single machine scheduling, Annals of Operations Research, 150, 3-15 (2007) · Zbl 1144.90375 |
| [4] | Armentano, V. A.; Ronconi, D. P., Tabu search for total tardiness minimization in flowshop scheduling problems, Computers & Operations Research, 26, 219-235 (1999) · Zbl 0947.90040 |
| [5] | Baker, K. R.; Smith, J. C., A multiple-criterion model for machine scheduling, Journal of Scheduling, 6, 7-16 (2003) · Zbl 1154.90406 |
| [6] | Browne, S.; Yechiali, U., Scheduling deteriorating jobs on a single processor, Operations Research, 38, 495-498 (1990) · Zbl 0703.90051 |
| [7] | Chen, Z. L., A note on single-processor scheduling with time-dependent execution times, Operations Research Letters, 17, 127-129 (1995) · Zbl 0841.90072 |
| [8] | Chen, J.-S.; Pan, J.-C.-H.; Wu, C.-K., Minimizing makespan in reentrant flow-shops using hybrid tabu search, International Journal of Advanced Manufacturing Technology, 34, 353-361 (2007) |
| [9] | Cheng, T. C.E.; Cheng, S. R.; Wu, W. H.; Hsu, P. H.; Wu, C.-C., A two-agent single- machine scheduling problem with truncated sum-of-processing- times-based learning considerations, Computers & Industrial Engineering, 60, 4, 534-541 (2011) |
| [10] | Cheng, T. C.E.; Wu, W. H.; Cheng, S. R.; Wu, C.-C., Two-agent scheduling with position- based deteriorating jobs and learning effects, Applied Mathematics and Computation, 217, 21, 8804-8824 (2011) · Zbl 1231.90182 |
| [11] | Cheng, T. C.E.; Chung, Y.-H.; Liao, S.-C.; Lee, W.-C., Two-agent singe- machine scheduling with release times to minimize the total weighted completion time, Computers & Operations Research, 40, 1, 353-361 (2013) · Zbl 1349.90329 |
| [12] | 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 |
| [13] | Cheng, S.-R., A single-machine two-agent scheduling problem by GA approach, Asia-Pacific Journal of Operational Research, 29, 2, 1250013-1-1250013-22 (2012) · Zbl 1246.90051 |
| [14] | Cheng, T. C.E.; Ng, C. T.; Yuan, J. J., Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs, Theoretical Computer Science, 362, 273-281 (2006) · Zbl 1100.68007 |
| [15] | Cheng, T. C.E.; Ng, C. T.; Yuan, J. J., Multi-agent scheduling on a single machine with max-form criteria, European Journal of Operational Research, 188, 603-609 (2008) · Zbl 1129.90023 |
| [16] | Della Croce, F.; Narayan, V.; Tadei, R., The two-machine total completion time flow shop problem, European Journal of Operational Research, 90, 227-237 (1996) · Zbl 0916.90148 |
| [17] | Ding, G.; Sun, S., Single-machine scheduling problems with two agents competing for makespan, Life System Modeling and Intelligent Computing, 6328/2010, 244-255 (2010) |
| [18] | Fisher, M. L., A dual algorithm for the one-machine scheduling problem, Mathematical Programming, 11, 229-251 (1971) · Zbl 0359.90039 |
| [19] | French, S., Sequencing and scheduling: an introduction to the mathematics of the job shop (1982), Ellis Horwood Limited · Zbl 0479.90037 |
| [20] | Gerstl, E.; Mosheiov, G., Scheduling problems with two competing agents to minimized weighted earliness-tardiness, Computers & Operations Research, 40, 1, 109-116 (2013) · Zbl 1349.90347 |
| [21] | Gupta, J. N.D.; Gupta, S. K., Single facility scheduling with nonlinear processing times, Computers and Industrial Engineering, 14, 387-393 (1988) |
| [22] | Gawiejnowicz, S., Time-dependent scheduling (2008), Springer-Verlag: Springer-Verlag Berlin, Heidelberg · Zbl 1155.90004 |
| [23] | Gawiejnowicz, S.; Lee, Lee W.-C.; Lin, C.-L.; Wu, C.-C., Single-machine scheduling of proportionally deteriorating jobs by two agents, Journal of the Operation Research Society, 62, 1983-1991 (2011) |
| [24] | Glover, F., Heuristics for integer programming using surrogate constraints, Decision Sciences, 8, 1, 156-166 (1977) |
| [25] | Glover, F., Tabu search—part I, INFORMS Journal on Computing, 190-206 (1989) · Zbl 0753.90054 |
| [26] | Janiak, A.; Krysiak, T.; Trela, R., Scheduling problems with learning and aging effects: a survey, Decision Making in Manufacturing and Services, 52, 19-36 (2011) · Zbl 1245.90031 |
| [28] | Liu, P.; Tang, L., Two-agent scheduling with linear deteriorating jobs on a single machine, Lecture Notes in Computer Science, 5092, 642-650 (2008) · Zbl 1148.90324 |
| [29] | Liu, P.; Zhou, X. Y.; Tang, L. X., Two-agent single-machine scheduling with position-dependent processing times, International Journal of Advanced Manufacturing Technology, 48, 32 (2010) |
| [30] | Li, D.-C.; Hsu, P.-H., Solving a two-agent single-machine scheduling problem considering learning effect, Computers & Operations Research, 39, 7, 1644-1651 (2012) · Zbl 1251.90165 |
| [31] | Liu, P.; Yi, N.; Zhou, X., Two-agent single-machine scheduling problems under increasing linear deterioration, Applied Mathematical Modelling, 35, 5, 2290-2296 (2011) · Zbl 1217.90108 |
| [32] | Lee, W. C.; Wang, W. J.; Shiau, Y. R.; Wu, C.-C., A single-machine scheduling problem with two-agent and deteriorating jobs, Applied Mathematical Modelling, 34, 10, 3098-3107 (2010) · Zbl 1201.90080 |
| [33] | Mor, B.; Mosheiov, G., Single machine batch scheduling with two competing agents to minimize total flowtime, European Journal of Operational Research, 215, 3, 524-531 (2011) · Zbl 1238.90069 |
| [34] | Ng, C. T.; Cheng, T. C.E.; Yuan, J. J., A note on the complexity of the problem of two-agent scheduling on a single machine, Journal of Combinatorial Optimization, 12, 387-394 (2006) · Zbl 1126.90027 |
| [35] | Sundararaghavan, P. S.; Kunnathur, A., Single machine scheduling with start time dependent processing time: Some solvable cases, European Journal of Operational Research, 78, 3, 394-403 (1994) · Zbl 0816.90088 |
| [36] | Wu, W.-H.; Cheng, S.-R.; Wu, C.-C.; Yin, Y., Ant colony algorithms for a two-agent scheduling with sum-of processing times-based learning and deteriorating considerations, Journal of Intelligent Manufacturing, 23, 5, 1985-1993 (2012) |
| [37] | Wu, C.-C.; Wu, W.-H.; Chen, J.-C.; Yin, Y.; Wu, W.-H., A study of the single-machine two-agent scheduling problem with release times, Applied Soft Computing, 13, 2, 998-1002 (2013) |
| [38] | Wu, C.-C.; Huang, S.-K.; Lee, W.-C., Two-agent scheduling with learning consideration, Computers & Industrial Engineering, 61, 4, 1324-1335 (2011) |
| [39] | Yuan, J. J.; Shang, W. P.; Feng, Q., A note on the scheduling with two families of jobs, Journal of Scheduling, 8, 537-542 (2005) · Zbl 1123.90040 |
| [40] | Yu, X.; Zhang, Y.; Xu, D.; Yin, Y., Single machine scheduling problem with two synergetic agents and piece-rate maintenance, Applied Mathematical Modelling, 37, 3, 1390-1399 (2013) · Zbl 1351.90105 |
| [41] | Yin, Y.; Cheng, S.-R.; Wu, C.-C., Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties, Information Sciences, 189, 282-292 (2012) · Zbl 1247.90165 |
| [42] | Yin, Y.; Wu, W.-H.; Cheng, S.-R.; Wu, C.-C., An investigation on a two-agent single-machine scheduling problem with unequal release dates, Computers & Operations Research, 39, 3062-3073 (2012) · Zbl 1349.90425 |
| [43] | Yin, Y.; Cheng, S.-R.; Cheng, T. C.E.; Wu, W.-H.; Wu, C.-C., Two-agent single-machine scheduling with release times and deadlines, International Journal of Shipping and Transport Logistics, 5, 1, 75-94 (2013) |
| [44] | Yin, Y.; Wu, C.-C.; Wu, W.-H.; Hsu, C.-J.; Wu, W.-H., A branch-and- bound procedure for a single-machine earliness scheduling problem with two agents, Applied Soft Computing, 13, 2, 1042-1054 (2013) |
| [45] | Yin, Y.; Cheng, S.-R.; Cheng, T. C.E.; Wu, C.-C.; Wu, W.-H., Two-agent single-machine scheduling with assignable due dates, Applied Mathematics and Computation, 219, 4, 1674-1685 (2012) · Zbl 1291.90102 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
