An Exact and Meta-heuristic Approach for Two-agent Single-machine Scheduling Problem

Wen-Hung Wu

《Journal of Marine Science and Technology》 21卷2期 (2013/04) Pp. 215-221

https://doi.org/10.6119/JMST-013-0128-1

並列摘要

In many real-life applications, it can be often found that multiple agents compete on the usage of a common processing resource in different application environments and different methodological fields, such as artificial intelligence, decision theory, operations research, etc. Moreover, scheduling with multiple agents is relatively unexplored. Based on this observation, this paper attempts to study a single-machine scheduling problem where the objective is to minimize the total tardiness of the first agent with the constraint that no tardy job is allowed for the second agent. In this study, we provide a branch-and-bound algorithm and a genetic algorithm for the optimal and near-optimal solutions. We also report a computational experiment to evaluate the impact of the parameters involving with proposed problem simulation settings.

並列關鍵字

scheduling ； single-machine ； two-agent ； genetic algorithm

參考文獻

Agnetis, A., Mirchandani, P. B., Pacciarelli, D., and Pacifici, A., “Sched- uling problems with two competing agents,” Operations Research, Vol. 52, pp. 229-242 (2004).

Bean, J. C., “Genetic algorithms and random keys for sequencing and optimization,” ORSA Journal of Computing, Vol. 6, pp. 154-160 (1994).

Chen, J. S., Pan, J. C. H., and Lin, C. M., “A hybrid genetic algorithm for the reentrant flowshop scheduling problem,” Expert Systems with Ap- plications, Vol. 34, pp. 570-577 (2008).

Cheng, T. C. E., Cheng, S.-R., Wu, W.-H., Hsu, P.-H., and Wu, C.-C., “A two-agent single-machine scheduling problem with truncated sum-of- processing-times-based learning considerations,” Computers and Indus- trial Engineering, Vol. 60, pp. 534-541 (2011).

Cheng, T. C. E., Ng, C. T., and Yuan, J. J., “Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs,” Theo- retical Computer Science, Vol. 362, pp. 273-281 (2006).