In order to investigate more realistic group scheduling problems with position-dependent effects,the model of general position-dependent group scheduling is proposed,where the actual group setup times and actual proce...In order to investigate more realistic group scheduling problems with position-dependent effects,the model of general position-dependent group scheduling is proposed,where the actual group setup times and actual processing times are described by general functions of the normal group setup time and position in the sequence.These general functions are not assumed to have specific function structures,and are not restricted to be monotone.By mathematical analysis and proof,each considered problem is decomposed into a group scheduling process and a job scheduling process,and each scheduling process is transferred into the classic assignment problem or the classic single-machine sequence problem,and then the computational complexity to solve the considered problem is analyzed.Analysis results show that,even with general position-dependent job processing times,both the single machine makespan minimization group scheduling problems and the parallel-machine total load minimization group scheduling problems remain polynomially solvable.展开更多
This paper focuses on solving a problem of improving system robustness and the efficiency of a distributed system at the same time. Fault tolerance with active replication and load balancing techniques are used. The p...This paper focuses on solving a problem of improving system robustness and the efficiency of a distributed system at the same time. Fault tolerance with active replication and load balancing techniques are used. The pros and cons of both techniques are analyzed, and a novel load balancing framework for fault tolerant systems with active replication is presented. Hierarchical architecture is described in detail. The framework can dynamically adjust fault tolerant groups and their memberships with respect to system loads. Three potential task scheduler group selection methods are proposed and simulation tests are made. Further analysis of test data is done and helpful observations for system design are also pointed out, including effects of task arrival intensity and task set size, relationship between total task execution time and single task execution time.展开更多
This paper presents the two-machine flowshop group scheduling problem with the optimal objective of maximum lateness. A dominance rule within group and a dominance rule between groups are established. These dominance ...This paper presents the two-machine flowshop group scheduling problem with the optimal objective of maximum lateness. A dominance rule within group and a dominance rule between groups are established. These dominance rules along with a previously established dominance rule are used to develop a heuristic algorithm. Experimental results are given and analyzed.展开更多
The hybrid flow shop group scheduling problem(HFGSP)with the delivery time windows has been widely studied owing to its better flexibility and suitability for the current just-in-time production mode.However,there are...The hybrid flow shop group scheduling problem(HFGSP)with the delivery time windows has been widely studied owing to its better flexibility and suitability for the current just-in-time production mode.However,there are several unresolved challenges in problem modeling and algorithmic design tailored for HFGSP.In our study,we place emphasis on the constraint of timeliness.Therefore,this paper first constructs a mixed integer linear programming model of HFGSP with sequence-dependent setup time and delivery time windows to minimize the total weighted earliness and tardiness(TWET).Then a penalty groups-assisted iterated greedy integrating idle time insertion(PG IG ITI)is proposed to solve the above problem.In the PG IG ITI,a double decoding strategy is proposed based on the earliest available machine rule and the idle time insertion rule to calculate the TWET value.Subsequently,to reduce the amount of computation,a skip-based destruction and reconstruction strategy is designed,and a penalty groups-assisted local search is proposed to further improve the quality of the solution by disturbing the penalized groups,i.e.,early and tardy groups.Finally,through comprehensive statistical experiments on 270 test instances,the results prove that the proposed algorithm is effective compared to four state-of-the-art algorithms.展开更多
Given that group technology can reduce the changeover time of equipment,broaden the productivity,and enhance the flexibility of manufacturing,especially cellular manufacturing,group scheduling problems(GSPs)have elici...Given that group technology can reduce the changeover time of equipment,broaden the productivity,and enhance the flexibility of manufacturing,especially cellular manufacturing,group scheduling problems(GSPs)have elicited considerable attention in the academic and industry practical literature.There are two issues to be solved in GSPs:One is how to allocate groups into the production cells in view of major setup times between groups and the other is how to schedule jobs in each group.Although a number of studies on GSPs have been published,few integrated reviews have been conducted so far on considered problems with different constraints and their optimization methods.To this end,this study hopes to shorten the gap by reviewing the development of research and analyzing these problems.All literature is classified according to the number of objective functions,number of machines,and optimization algorithms.The classical mathematical models of single-machine,permutation,and distributed flowshop GSPs based on adjacent and position-based modeling methods,respectively,are also formulated.Last but not least,outlooks are given for outspread problems and problem algorithms for future research in the fields of group scheduling.展开更多
Scheduling with group technology has been a vivid research area in the past decades.However,group technology with general dual-effect variable processing times needs to be further explored although this kind of group...Scheduling with group technology has been a vivid research area in the past decades.However,group technology with general dual-effect variable processing times needs to be further explored although this kind of group technology plays an important role in some actual manufacturing scenarios.Accordingly,this paper considers group scheduling problems with a kind of general group variable processing times model,where the actual processing time of each job in group is variable due to the dual effect of both the job position and the group position.The objectives of two types of considered problems are to minimize the makespan and the total completion time,respectively.Based on the decomposition analysis,the mathematical logic analysis and the computational complexity proof,it is obtained that the makespan minimization problem and the total completion time minimization problem are both polynomially solvable under the condition that the group number is constant.For three special cases of considered problems,polynomial solving algorithms with lower computational complexity are proposed.展开更多
基金The National Natural Science Foundation of China (No.71171046)the Scientific Research Innovation Project for College Graduates in Jiangsu Province(No.CXLX_0162)
文摘In order to investigate more realistic group scheduling problems with position-dependent effects,the model of general position-dependent group scheduling is proposed,where the actual group setup times and actual processing times are described by general functions of the normal group setup time and position in the sequence.These general functions are not assumed to have specific function structures,and are not restricted to be monotone.By mathematical analysis and proof,each considered problem is decomposed into a group scheduling process and a job scheduling process,and each scheduling process is transferred into the classic assignment problem or the classic single-machine sequence problem,and then the computational complexity to solve the considered problem is analyzed.Analysis results show that,even with general position-dependent job processing times,both the single machine makespan minimization group scheduling problems and the parallel-machine total load minimization group scheduling problems remain polynomially solvable.
文摘This paper focuses on solving a problem of improving system robustness and the efficiency of a distributed system at the same time. Fault tolerance with active replication and load balancing techniques are used. The pros and cons of both techniques are analyzed, and a novel load balancing framework for fault tolerant systems with active replication is presented. Hierarchical architecture is described in detail. The framework can dynamically adjust fault tolerant groups and their memberships with respect to system loads. Three potential task scheduler group selection methods are proposed and simulation tests are made. Further analysis of test data is done and helpful observations for system design are also pointed out, including effects of task arrival intensity and task set size, relationship between total task execution time and single task execution time.
文摘This paper presents the two-machine flowshop group scheduling problem with the optimal objective of maximum lateness. A dominance rule within group and a dominance rule between groups are established. These dominance rules along with a previously established dominance rule are used to develop a heuristic algorithm. Experimental results are given and analyzed.
基金This work was supported by the Natural Science Foundation of Shandong province(No.ZR2023MF022)National Natural Science Foundation of China(Nos.61973203,61803192,62106073,and 61966012)Guangyue Young Scholar Innovation Team of Liaocheng University(No.LCUGYTD2022-03).
文摘The hybrid flow shop group scheduling problem(HFGSP)with the delivery time windows has been widely studied owing to its better flexibility and suitability for the current just-in-time production mode.However,there are several unresolved challenges in problem modeling and algorithmic design tailored for HFGSP.In our study,we place emphasis on the constraint of timeliness.Therefore,this paper first constructs a mixed integer linear programming model of HFGSP with sequence-dependent setup time and delivery time windows to minimize the total weighted earliness and tardiness(TWET).Then a penalty groups-assisted iterated greedy integrating idle time insertion(PG IG ITI)is proposed to solve the above problem.In the PG IG ITI,a double decoding strategy is proposed based on the earliest available machine rule and the idle time insertion rule to calculate the TWET value.Subsequently,to reduce the amount of computation,a skip-based destruction and reconstruction strategy is designed,and a penalty groups-assisted local search is proposed to further improve the quality of the solution by disturbing the penalized groups,i.e.,early and tardy groups.Finally,through comprehensive statistical experiments on 270 test instances,the results prove that the proposed algorithm is effective compared to four state-of-the-art algorithms.
基金This work is partially supported by the National Natural Science Foundation of China(Grant Nos.61803192,61966012,61973203,and 62106073)Guangyue Young Scholar Innovation Team of Liaocheng University(Grant No.LCUGYTD2022-03)+1 种基金the Youth Innovation Talent Introduction and Education Program support from Shandong Province Colleges and Universities,the Natural Science Foundation of Hunan Province(Grant No.2021JJ40116)the Natural Science Foundation of Shandong Province(Grant Nos.ZR2021QE195 and ZR2021QF036).
文摘Given that group technology can reduce the changeover time of equipment,broaden the productivity,and enhance the flexibility of manufacturing,especially cellular manufacturing,group scheduling problems(GSPs)have elicited considerable attention in the academic and industry practical literature.There are two issues to be solved in GSPs:One is how to allocate groups into the production cells in view of major setup times between groups and the other is how to schedule jobs in each group.Although a number of studies on GSPs have been published,few integrated reviews have been conducted so far on considered problems with different constraints and their optimization methods.To this end,this study hopes to shorten the gap by reviewing the development of research and analyzing these problems.All literature is classified according to the number of objective functions,number of machines,and optimization algorithms.The classical mathematical models of single-machine,permutation,and distributed flowshop GSPs based on adjacent and position-based modeling methods,respectively,are also formulated.Last but not least,outlooks are given for outspread problems and problem algorithms for future research in the fields of group scheduling.
基金the National Natural Science Foundation of China(No.71573121)China Postdoctoral Science Foundation Funded Project(No.2016M590453)the Fundamental Research Funds for the Central Universities(Nos.NS2016080 and NR2016005).
文摘Scheduling with group technology has been a vivid research area in the past decades.However,group technology with general dual-effect variable processing times needs to be further explored although this kind of group technology plays an important role in some actual manufacturing scenarios.Accordingly,this paper considers group scheduling problems with a kind of general group variable processing times model,where the actual processing time of each job in group is variable due to the dual effect of both the job position and the group position.The objectives of two types of considered problems are to minimize the makespan and the total completion time,respectively.Based on the decomposition analysis,the mathematical logic analysis and the computational complexity proof,it is obtained that the makespan minimization problem and the total completion time minimization problem are both polynomially solvable under the condition that the group number is constant.For three special cases of considered problems,polynomial solving algorithms with lower computational complexity are proposed.