A PMBGA to Optimize the Selection of Rules for Job Shop Scheduling Based on the Giffler-Thompson Algorithm
Most existing research on the job shop scheduling problem has been focused on the minimization of makespan (i.e., the completion time of the last job). However, in the fiercely competitive market nowadays, delivery punctuality is more important for maintaining a high service reputation. So in this p...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2012-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2012/623230 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832555914523049984 |
|---|---|
| author | Rui Zhang Cheng Wu |
| author_facet | Rui Zhang Cheng Wu |
| author_sort | Rui Zhang |
| collection | DOAJ |
| description | Most existing research on the job shop scheduling problem has been focused on the minimization of makespan (i.e., the completion time of the last job). However, in the fiercely competitive market nowadays, delivery punctuality is more important for maintaining a high service reputation. So in this paper, we aim at solving job shop scheduling problems with the total weighted tardiness objective. Several dispatching rules are adopted in the Giffler-Thompson algorithm for constructing active schedules. It is noticeable that the rule selections for scheduling consecutive operations are not mutually independent but actually interrelated. Under such circumstances, a probabilistic model-building genetic algorithm (PMBGA) is proposed to optimize the sequence of selected rules. First, we use Bayesian networks to model the distribution characteristics of high-quality solutions in the population. Then, the new generation of individuals is produced by sampling the established Bayesian network. Finally, some elitist individuals are further improved by a special local search module based on parameter perturbation. The superiority of the proposed approach is verified by extensive computational experiments and comparisons. |
| format | Article |
| id | doaj-art-396f2a63c19f43f8ae00f4421b2decc7 |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2012-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-396f2a63c19f43f8ae00f4421b2decc72025-02-03T05:46:51ZengWileyJournal of Applied Mathematics1110-757X1687-00422012-01-01201210.1155/2012/623230623230A PMBGA to Optimize the Selection of Rules for Job Shop Scheduling Based on the Giffler-Thompson AlgorithmRui Zhang0Cheng Wu1School of Economics and Management, Nanchang University, Nanchang 330031, ChinaDepartment of Automation, Tsinghua University, Beijing 100084, ChinaMost existing research on the job shop scheduling problem has been focused on the minimization of makespan (i.e., the completion time of the last job). However, in the fiercely competitive market nowadays, delivery punctuality is more important for maintaining a high service reputation. So in this paper, we aim at solving job shop scheduling problems with the total weighted tardiness objective. Several dispatching rules are adopted in the Giffler-Thompson algorithm for constructing active schedules. It is noticeable that the rule selections for scheduling consecutive operations are not mutually independent but actually interrelated. Under such circumstances, a probabilistic model-building genetic algorithm (PMBGA) is proposed to optimize the sequence of selected rules. First, we use Bayesian networks to model the distribution characteristics of high-quality solutions in the population. Then, the new generation of individuals is produced by sampling the established Bayesian network. Finally, some elitist individuals are further improved by a special local search module based on parameter perturbation. The superiority of the proposed approach is verified by extensive computational experiments and comparisons.http://dx.doi.org/10.1155/2012/623230 |
| spellingShingle | Rui Zhang Cheng Wu A PMBGA to Optimize the Selection of Rules for Job Shop Scheduling Based on the Giffler-Thompson Algorithm Journal of Applied Mathematics |
| title | A PMBGA to Optimize the Selection of Rules for Job Shop Scheduling Based on the Giffler-Thompson Algorithm |
| title_full | A PMBGA to Optimize the Selection of Rules for Job Shop Scheduling Based on the Giffler-Thompson Algorithm |
| title_fullStr | A PMBGA to Optimize the Selection of Rules for Job Shop Scheduling Based on the Giffler-Thompson Algorithm |
| title_full_unstemmed | A PMBGA to Optimize the Selection of Rules for Job Shop Scheduling Based on the Giffler-Thompson Algorithm |
| title_short | A PMBGA to Optimize the Selection of Rules for Job Shop Scheduling Based on the Giffler-Thompson Algorithm |
| title_sort | pmbga to optimize the selection of rules for job shop scheduling based on the giffler thompson algorithm |
| url | http://dx.doi.org/10.1155/2012/623230 |
| work_keys_str_mv | AT ruizhang apmbgatooptimizetheselectionofrulesforjobshopschedulingbasedonthegifflerthompsonalgorithm AT chengwu apmbgatooptimizetheselectionofrulesforjobshopschedulingbasedonthegifflerthompsonalgorithm AT ruizhang pmbgatooptimizetheselectionofrulesforjobshopschedulingbasedonthegifflerthompsonalgorithm AT chengwu pmbgatooptimizetheselectionofrulesforjobshopschedulingbasedonthegifflerthompsonalgorithm |