The digital industrial revolution continues to expand the global network of economies and societies. Nevertheless, difficulties of sustainability such as climate change and disruption have become more severe. Multi-stakeholders are crucially important to resolve difficulties posed to sustainability in global communities. Sustainable communities are expected to be constructed through competitive and cooperative schemes of multi-stakeholders. Sustainable global communities must reform centralized economies with top down systems and must move toward decentralized mechanisms known as bottom-up societies. Sustainable investment strategies to support environment, society and governance (ESG) presumably improve social welfare. The main findings presented herein are summarized as explained hereinafter. First, this article describes that multi-stakeholders can introduce a decentralized incentive scheme into global economies and can provide mathematical expressions of sustainable investment strategies. Secondly, the decentralized formulation described herein is used to evaluate the improvement of ESG initiatives by the decrease of social welfare losses. The formulation states mathematically relative relations among the investment strategies. Thirdly, this mathematical model explores the social welfare effects of initiatives to enhance standards, regulations, and legislations. Empirically, one finds that integration strategies have grown remarkably as a core part of social institutional reform for sustainability. Finally, initiatives to improve social evaluation by individuals who are excluded from market transaction are demonstrated to decrease social welfare losses greatly. These findings can promote initiatives to alleviate the disruption difficulties faced by communities.
Citation: Hiroshige Tanaka, Chiharu Tanaka. Sustainable investment strategies and a theoretical approach of multi-stakeholder communities[J]. Green Finance, 2022, 4(3): 329-346. doi: 10.3934/GF.2022016
[1] | Shuguang Li, Zhimeng Liu . Scheduling uniform machines with restricted assignment. Mathematical Biosciences and Engineering, 2022, 19(9): 9697-9708. doi: 10.3934/mbe.2022450 |
[2] | Xue Jia, Jing Xue, Shi-Yun Wang, Ji-Bo Wang . Polynomial time algorithm for minmax scheduling with common due-window and proportional-linear shortening processing times. Mathematical Biosciences and Engineering, 2022, 19(9): 8923-8934. doi: 10.3934/mbe.2022414 |
[3] | Guohui Zhang, Jinghe Sun, Xing Liu, Guodong Wang, Yangyang Yang . Solving flexible job shop scheduling problems with transportation time based on improved genetic algorithm. Mathematical Biosciences and Engineering, 2019, 16(3): 1334-1347. doi: 10.3934/mbe.2019065 |
[4] | Dan Yang, Zhiqiang Xie, Chunting Zhang . Multi-flexible integrated scheduling algorithm for multi-flexible integrated scheduling problem with setup times. Mathematical Biosciences and Engineering, 2023, 20(6): 9781-9817. doi: 10.3934/mbe.2023429 |
[5] | Weiguo Liu, Xuyin Wang, Lu Li, Peizhen Zhao . A maintenance activity scheduling with time-and-position dependent deteriorating effects. Mathematical Biosciences and Engineering, 2022, 19(11): 11756-11767. doi: 10.3934/mbe.2022547 |
[6] | Zhimeng Liu, Shuguang Li . Pareto optimal algorithms for minimizing total (weighted) completion time and maximum cost on a single machine. Mathematical Biosciences and Engineering, 2022, 19(7): 7337-7348. doi: 10.3934/mbe.2022346 |
[7] | Jianguo Duan, Mengting Wang, Qinglei Zhang, Jiyun Qin . Distributed shop scheduling: A comprehensive review on classifications, models and algorithms. Mathematical Biosciences and Engineering, 2023, 20(8): 15265-15308. doi: 10.3934/mbe.2023683 |
[8] | Xuyin Wang, Weiguo Liu, Lu Li, Peizhen Zhao, Ruifeng Zhang . Resource dependent scheduling with truncated learning effects. Mathematical Biosciences and Engineering, 2022, 19(6): 5957-5967. doi: 10.3934/mbe.2022278 |
[9] | Lu-Wen Liao . A branch and bound algorithm for optimal television commercial scheduling. Mathematical Biosciences and Engineering, 2022, 19(5): 4933-4945. doi: 10.3934/mbe.2022231 |
[10] | Cong Zhao, Na Deng . An actor-critic framework based on deep reinforcement learning for addressing flexible job shop scheduling problems. Mathematical Biosciences and Engineering, 2024, 21(1): 1445-1471. doi: 10.3934/mbe.2024062 |
The digital industrial revolution continues to expand the global network of economies and societies. Nevertheless, difficulties of sustainability such as climate change and disruption have become more severe. Multi-stakeholders are crucially important to resolve difficulties posed to sustainability in global communities. Sustainable communities are expected to be constructed through competitive and cooperative schemes of multi-stakeholders. Sustainable global communities must reform centralized economies with top down systems and must move toward decentralized mechanisms known as bottom-up societies. Sustainable investment strategies to support environment, society and governance (ESG) presumably improve social welfare. The main findings presented herein are summarized as explained hereinafter. First, this article describes that multi-stakeholders can introduce a decentralized incentive scheme into global economies and can provide mathematical expressions of sustainable investment strategies. Secondly, the decentralized formulation described herein is used to evaluate the improvement of ESG initiatives by the decrease of social welfare losses. The formulation states mathematically relative relations among the investment strategies. Thirdly, this mathematical model explores the social welfare effects of initiatives to enhance standards, regulations, and legislations. Empirically, one finds that integration strategies have grown remarkably as a core part of social institutional reform for sustainability. Finally, initiatives to improve social evaluation by individuals who are excluded from market transaction are demonstrated to decrease social welfare losses greatly. These findings can promote initiatives to alleviate the disruption difficulties faced by communities.
The problem of scheduling uniform parallel batch machines with processing set restrictions can be defined as follows. Let J={1,2,…,n} be a set of jobs and M={M1,M2,…,Mm} be a set of uniform parallel batch machines. Job j (j=1,2,…,n) becomes available at its release time rj≥0 and requires pj≥0 units of processing called its length. For each job j, let Mj⊆M be the set of the eligible machines which are capable of processing the job, called its processing set. Each job will be assigned to exactly one machine and job preemption is not allowed. Machine Mi (i=1,2,…,m) has a speed vi≥1 and a capacity Ki<n. The impact of the speed is that Mi can carry out vi units of processing in one time unit. That is, if job j is assigned to machine Mi, then it requires pj/vi processing time to be completed. Machine Mi can process several jobs as a batch simultaneously as long as the total number of these jobs does not exceed Ki. The length of a batch is the maximum of the lengths of the jobs belonging to it. Jobs in the same batch have a common start time and a common completion time. The goal is to schedule the jobs on the machines in a manner that optimizes one or more objective functions.
Two classes of objectives are considered: the min-sum objective and the min-max objective. Specifically, let fj:[0,+∞)→[0,+∞) (j=1,2,…,n) be a non-decreasing function. Additional parameters that may be included for job j are its due date dj and its weight wj. For a particular schedule σ, let Cj(σ) denote the completion time of job j in σ. Let Tj(σ)=max{Cj(σ)−dj,0} denote the tardiness of job j in σ. Let Uj(σ)=1 if Cj(σ)>dj and Uj(σ)=0 otherwise. (In the rest of this paper, we safely ignore σ in the notations without causing confusion.) The objectives of minimizing ∑nj=1fj(Tj) and maxj=1,2,…,n{fj(Tj)} will be considered. Following [1,2], the models can be denoted as Q|rj,dj,Mj,p−batch,Ki|∑fj(Tj) and Q|rj,dj,Mj,p−batch,Ki|max{fj(Tj)}.
Many popular scheduling objectives are covered by the two models, such as total weighted completion time (∑wjCj) minimization, total weighted tardiness (∑wjTj) minimization, weighted number of tardy jobs (∑wjUj) minimization, makespan (Cmax=maxCj) minimization, and maximum weighted tardiness (max{wj(Tj)}) minimization. As shown in [3,4,5], most of such problems are NP-hard even for the special cases where all vi=1, all Ki=1 and all Mj=M. Thus, we are interested in polynomial time exact algorithms for some important special cases of the problems [6].
In this paper, we focus on an important special case where all jobs have equal lengths (and equal release times). The problems under study can be denoted as Q|pj=p,dj,Mj,p−batch,Ki|∑fj(Tj) (the special case of Q|rj,pj=p,dj,Mj,p−batch,Ki|∑fj(Tj) where all rj=0) and Q|pj=p,dj,Mj,p−batch,Ki|max{fj(Tj)} (the special case of Q|rj,pj=p,dj,Mj,p−batch,Ki|max{fj(Tj)} where all rj=0). Li [7] presented polynomial time algorithms for uniform parallel machine scheduling problems Q|pj=p,dj,Mj|∑fj(Tj) and Q|pj=p,dj,Mj|max{fj(Tj)} (the special cases of Q|pj=p,dj,Mj,p−batch,Ki|∑fj(Tj) and Q|pj=p,dj,Mj,p−batch,Ki|max{fj(Tj)} where all Ki=1). We extend the results obtained in [7] to uniform parallel batch machines, allowing the machines to have non-identical capacities. Moreover, for minimizing makespan, we allow unequal release times and get an algorithm for arbitrary processing set restrictions.
Although the above problem setting appears simple, it captures important aspects of a wide range of applications. There are many problems arise as its special or similar cases in networking and information systems. For example, Low [8] studied the problem in the context of retrieving data blocks from disks in video on demand systems. Suri et al. [9] considered the problem in peer-to-peer systems. The problem was also studied for workload balancing among packet queues [10], for data aggregation in wireless sensor networks [11]. Recently, Champati and Liang [12] studied a very similar problem where each machine has its own convex cost functions, aiming to minimize the sum cost and the maximum differential cost of the machines.
The remainder of this paper is organized as follows. In Section 2, the related researches are reviewed. In Section 3, we consider the case of equal release times. We present an algorithm with running time O(n3m+n2mlog(mn)) for Q|pj=p,dj,Mj,p−batch,Ki|∑fj(Tj), as well as an algorithm with running time O(n5/2m3/2log(mn)) for Q|pj=p,dj,Mj,p−batch,Ki|max{fj(Tj)}. In Section 4, we consider the case of unequal release times. We present an algorithm with running time O(n5/2m3/2log(mn)) for Q|rj,pj=p,Mj,p−batch,Ki|Cmax. Section 5 presents the conclusions and future directions of research.
Leung and Li [13] discussed several special cases of processing set restrictions. The processing sets of the jobs are inclusive, if for any two jobs j1 andj2, either Mj1⊆Mj2, or Mj2⊆Mj1. The processing sets are nested, if for any two jobs j1 andj2, either Mj1∩Mj2=∅, or Mj1⊆Mj2, or Mj2⊆Mj1. The processing sets are interval, if for any job j, Mj={Maj,Maj+1,…,Mbj} for some 1≤aj≤bj≤m. The processing sets are tree-hierarchical, if each machine is represented by a tree node, and each job j is associated with a tree node Maj, such that Mj is exactly the set of the machines consisting of all the nodes on the unique path from Maj to the root of the tree.
The problem studied in this paper combines two important sub-fields of scheduling theory: scheduling with processing set restrictions and parallel batch scheduling. The two sub-fields have received intense study in the literature, see the survey papers [13] and [14,15,16] respectively. There are also a few papers which combined the two-subfields into a unified framework [17,18,19,20,21,22,23]. In the problems studied in these papers except the last two, each job has a size and a machine can process several jobs simultaneously as a batch as long as the total size of these jobs does not exceed its capacity. Any machine cannot process the jobs whose sizes are larger than its capacity. Thus, for each job, the machines whose capacities are not less than its size form its processing set. Clearly, the processing sets of the jobs are inclusive. In [22], Li presented two algorithms with approximation ratios 3 and 9/4 for the problem of minimizing makespan on parallel batch machines with inclusive processing set restrictions, where the jobs have arbitrary lengths and the machines have the same speed. In [23], Li studied parallel batch scheduling with nested processing set restrictions to minimize makespan, and presented a (3−1/m)-approximation algorithm for the case of equal release times and a polynomial time approximation scheme (PTAS) for the case of unequal release times.
For scheduling with processing set restrictions, the review focuses on the case of equal job lengths. Lin and Li [24] obtained an algorithm for P|pj=p,Mj|Cmax (the special case of Q|rj,pj=p,Mj|Cmax where all rj=0 and all vi=1) that runs in O(n3logn) time, and generalized the algorithm to solve Q|pj=p,Mj|Cmax in O(n3log(nvlcm)) time, where vlcm denotes the least common multiple of v1,v2,…,vm. They also obtained an algorithm for P|pj=p,Mj(interval)|Cmax (the special case of P|pj=p,Mj|Cmax with interval processing set restrictions) that runs in O(m2+mn) time. Harvey et al. [25] independently developed an algorithm for P|pj=p,Mj|Cmax that runs in O(n2m) time. Brucker et al. [26] presented algorithms running in O(n2m(n+logm)) time for Q|pj=p,dj,Mj|∑wjTj, Q|pj=p,dj,Mj|∑wjUj, P|rj,pj=1,dj,Mj|∑wjTj and P|rj,pj=1,dj,Mj|∑wjUj. Li [7] presented an algorithm for Q|pj=p,dj,Mj|∑fj(Tj) that runs in O(n3m+n2mlog(mn)) time. For the special cases where fj(Tj)=Cj or fj(Tj)=Uj, the running time of the algorithm can be improved to O(n5/2mlogn). He also presented an algorithm for Q|pj=p,dj,Mj|max{fj(Tj)} that runs in O(n5/2mlog(mn)) time. For the special cases where fj(Tj)=Cj (i.e., Q|pj=p,Mj|Cmax), the running time of the algorithm can be improved to O(n2(m+log(nvmax))logn), where vmax=max{vj}. Lee et al. [27] showed that Q|rj,pj=p,Mj|Cmax can be solved in O(m3/2n5/2log(mn)) time, and P|rj,pj=p,Mj|Cmax(the special case of Q|rj,pj=p,Mj|Cmax where all vi=1) can be solved in O(m3/2n5/2logn) time. Shabtay et al. [28] obtained various results for several problems of scheduling uniform machines with equal length jobs, processing set restrictions and job rejection. Hong et al. [29] studied P|rj,pj=p,Mj|∑Cj. For the problem with a fixed number of machines, they provided a polynomial time dynamic programming algorithm. For the general case, they presented two polynomial time approximation algorithms with approximation ratios 3/5 and 5/7 respectively. Jiang et al. [30] presented a comprehensive overview (including their new findings) of ideal schedules for various scheduling problems in different machine environments and with different job characteristics. An ideal schedule is a schedule that simultaneously minimizes the total completion time and makespan. They pointed out that in most problems that are known to have an ideal schedule, the jobs have equal processing times. Along with other results, they proved that any optimal schedule for Q|pj=p,Mj|∑Cj also minimizes makespan. Jing et al. [31] studied the problem of scheduling high multiplicity jobs to minimize makespan on parallel machines with processing set restrictions, setup times and machine available times. High multiplicity means that jobs are partitioned into several groups and in each group all jobs are identical. Whenever there is a switch from processing a job of one group to a job of another group, a setup time is needed. They formulated the problem as a mixed integer programming and proposed a heuristic for it.
Pinedo [32] and Glass and Mills [33] presented algorithms for P|pj=p,Mj(nested)|Cmax (the special case of P|pj=p,Mj|Cmax with nested processing set restrictions) that run in time O(nlogn) and O(m2) time respectively. Li and Li [34] presented algorithms for P|rj,pj=p,Mj(inclusive)|Cmax and P|rj,pj=p,Mj(tree)|Cmax (the special cases of P|rj,pj=p,Mj|Cmax with inclusive and tree-hierarchical processing set restrictions) that run in O(n2+mnlogn) time. For uniform machines, they showed that Q|rj,pj=p,Mj(inclusive)|Cmax and Q|rj,pj=p,Mj(tree)|Cmax can be solved in O(mn2logm) time. Later, Li and Lee [35] developed an improved algorithm for P|rj,pj=p,Mj(inclusive)|Cmax that runs in O(min{m,logn}nlogn) time, and an improved algorithm for P|rj,pj=p,Mj(tree)|Cmax that runs in O(mnlogn) time.
For parallel batch scheduling, the review focuses on equal job lengths or uniform parallel batch machines. Liu et al. [36] presented an algorithm for P|rj,pj=p,p−batch,B|Cmax (the special case of Q|rj,pj=p,Mj,p−batch,Ki|Cmax where all Mj=M, all Ki=B and all vi=1) that runs in O(nlogn) time. Ozturk et al. [37] presented a 2-approximation algorithm for the problem of scheduling jobs with equal lengths, unequal release times and sizes on identical parallel batch machines (all Ki=B) to minimize makespan. Wang and Leung [18] studied the problem of scheduling jobs with equal lengths and arbitrary sizes on parallel batch machines (all vi=1) with non-identical capacities. The problem fits into the model of scheduling with inclusive processing set restrictions, since each job can only be processed by the machines whose capacities are not less than the size of the job. Wang and Leung [18] presented a 2-approximation algorithm, as well as an algorithm with asymptotic approximation ratio 3/2 for the problem. Li et al. [38] proposed several heuristics for the problem of scheduling jobs with unequal lengths, release times and sizes on uniform parallel batch machines with identical capacities to minimize makespan. Zhou et al. [39] presented an effective discrete differential evolution algorithm for the problem of scheduling jobs with unequal lengths and sizes on uniform parallel batch machines with non-identical capacities to minimize makespan. Both [38] and [39] have not included processing set restrictions.
In this section, we consider the case of equal release times. We will present algorithms for Q|pj=p,dj,Mj,p−batch,Ki|∑fj(Tj) and Q|pj=p,dj,Mj,p−batch,Ki|max{fj(Tj)}.
Since fj (j=1,2,…,n) is a non-decreasing function, for both Q|pj=p,dj,Mj,p−batch,Ki|∑fj(Tj) and Q|pj=p,dj,Mj,p−batch,Ki|max{fj(Tj)}, there is an optimal schedule in which the first batch on each machine starts at time zero, and the batches on each machine are processed successively. Moreover, we can assume that there are ni empty batches on machine Mi (i=1,2,…,m) to which the jobs may be assigned, where ni denotes the smallest integer such that niKi≥n. The k-th batch on Mi, Bk,i, completes at time kp/vi, k=1,2,…,ni. To find a feasible schedule, we need only to assign the jobs to ∑mi=1ni empty batches such that all jobs obey the processing set restrictions.
First, we consider Q|pj=p,dj,Mj,p−batch,Ki|∑fj(Tj).
If job j is assigned to Bk,i and Mi∈Mj, then the cost incurred is defined to be cjki=fj(max{kp/vi−dj,0}), j=1,2,…,n, k=1,2,…,ni, i=1,2,…,m. Let C=maxj,k,icjki. By regarding each job j∈J as a vertex in X, and each empty batch Bk,i as Ki vertices yk1,yk2,…,ykKi in Y, we construct a bipartite graph G with bipartition (X,Y), where j is joined to yk1,yk2,…,ykKi if and only if Mi∈Mj, and the incurred costs are equal to cjki, j=1,2,…,n, k=1,2,…,ni, i=1,2,…,m. Then we use the Successive Shortest Path algorithm to solve the bipartite weighted matching problem [40] and get a matching of minimum cost that saturates every vertex in X. From this matching we can construct an optimal schedule easily.
The Successive Shortest Path algorithm runs in O(|X|⋅S(|X|+|Y|,|X||Y|,C)) time, where S(|X|+|Y|,|X||Y|,C) is the time for solving a shortest path problem with |X|+|Y| vertices, |X||Y| edges (these edges have non-negative costs), and maximum coefficient C. Currently, S(u,a,C)=O(a+ulogu) [41]. Note that |X|=n and |Y|≤2mn. We get:
Theorem 3.1. There is an exact algorithm for Q|pj=p,dj,Mj,p−batch,Ki|∑fj(Tj) that runs in O(n3m+n2mlog(mn)) time.
Next, we consider Q|pj=p,dj,Mj,p−batch,Ki|max{fj(Tj)}. Let OPT denote the objective value of an optimal schedule.
Recall that we are focusing on an optimal schedule in which machine Mi (i=1,2,…,m) processes ni batches (some batches may be empty), where ni denotes the smallest integer such that niKi≥n. Each batch on Mi has Ki positions to accommodate jobs, and there are at most 2n positions on Mi, i=1,2,…,m. Therefore, there are at most 2mn positions in total. Since each position has at most n choices of accommodating a job, there are at most 2mn2 possible values for OPT. We can sort these values in ascending order in O(mn2log(mn)) time. Then, we perform a binary search in the interval to determine OPT in O(log(mn)) iterations.
For each value λ selected, we test whether there is a feasible schedule whose objective value is no more than λ. To this end, we construct a bipartite graph G with bipartition (X,Y) as follows. Regard each job j∈J as a vertex in X, and each empty batch Bk,i as Ki vertices yk1,yk2,…,ykKi in Y, where j is joined to yk1,yk2,…,ykKi if and only if Mi∈Mj and fj(kp/vi−dj)≤λ, j=1,2,…,n, k=1,2,…,ni, i=1,2,…,m. Then we use the algorithm in [42] to solve the maximum cardinality bipartite matching problem. If the obtained matching saturates every vertex in X, then the procedure succeeds and we search the lower half of the interval. Otherwise, the procedure fails and we search the upper half of the interval.
The algorithm in [42] runs in O(√|X|+|Y|⋅|X||Y|) time. Note that |X|=n and |Y|≤2mn. We get:
Theorem 3.2. There is an exact algorithm for Q|pj=p,dj,Mj,p−batch,Ki|max{fj(Tj)} that runs in O(n5/2m3/2log(mn)) time.
In this section, we consider the case of unequal release times. We will present an algorithm for Q|rj,pj=p,Mj,p−batch,Ki|Cmax, which generalizes the one in [27] for Q|rj,pj=p,Mj|Cmax (the special case of Q|rj,pj=p,Mj,p−batch,Ki|Cmax where all Ki=1). Let OPT denote the makespan of an optimal schedule for Q|rj,pj=p,Mj,p−batch,Ki|Cmax. Let Λ= {λ|λ=rj+kp/vi;j,k∈{1,2,…n} and i∈{1,2,…m}}. The following lemma, adopted from [27], still holds for Q|rj,pj=p,Mj,p−batch,Ki|Cmax.
Lemma 4.1. The set Λ, as defined above, contains all candidates for OPT.
Since |Λ|≤mn2, there are at most mn2 possible values for OPT. We can sort these values in ascending order in O(mn2log(mn)) time. Then, we perform a binary search to determine OPT in O(log(mn)) iterations.
For each value λ selected, we use the following procedure, AssignJobs, to test whether there is a feasible schedule whose makespan is no more than λ.
AssignJobs (λ):
Step 1. Assign bi=min{ni,⌊λ⋅vi/p⌋} empty batches of length p and capacity Ki to machine Mi, where ni denotes the smallest integer such that niKi≥n. The k-th batch on Mi, Bk,i, starts at time λ−(bi−k+1)p/vi and completes at time λ−(bi−k)p/vi, k=1,2,…,bi, i=1,2,…,m.
Step 2. Construct a bipartite graph G with bipartition (X,Y) as follows. Regard each job j∈J as a vertex in X, and each empty batch Bk,i as Ki vertices yk1,yk2,…,ykKi in Y, where j is joined to yk1,yk2,…,ykKi if and only if Mi∈Mj and rj≤λ−(bi−k+1)p/vi, j=1,2,…,n, k=1,2,…,bi, i=1,2,…,m.
Step 3. Use the algorithm in [42] to solve the maximum cardinality bipartite matching problem. If the obtained matching saturates every vertex in X, then the procedure succeeds and terminates. Otherwise, the procedure fails and terminates.
Lemma 4.2. If OPT≤λ, then AssignJobs will generate a feasible schedule in O(n5/2m3/2) time for Q|rj,pj=p,Mj,p−batch,Ki|Cmax whose makespan is at most λ.
Proof. Let σ∗ denote an optimal schedule. Consider machine Mi, i=1,2,…,m. Since OPT≤λ, in σ∗, Mi processes at most bi batches. Without loss of generality, assume that there are bi batches (some of which may be dummy empty batches) processed on Mi in σ∗, denoted as B∗1,i,B∗2,i,…B∗bi,i.
Modify σ∗ as follows. Let B∗bi,i be completed at time λ, B∗bi−1,i be completed at time λ−p/vi, ..., B∗1,i be completed at time λ−(bi−1)p/vi, i=1,2,…,m. Denote by ˜σ∗ the modified schedule. Since each batch in ˜σ∗ starts no earlier than its corresponding batch in σ∗, ˜σ∗ is a feasible schedule. The makespan of ˜σ∗ is exactly λ. Clearly, AssignJobs will generate a feasible schedule which is no worse than ˜σ∗.
The algorithm in [42] runs in O(√|X|+|Y|⋅|X||Y|) time. Since |X|=n and |Y|≤2mn, the running time of AssignJobs is O(n5/2m3/2).
We get:
Theorem 4.3. There is an exact algorithm for Q|rj,pj=p,Mj,p−batch,Ki|Cmax that runs in O(n5/2m3/2log(mn)) time.
We studied the problem of scheduling jobs with equal lengths and processing set restrictions on uniform parallel batch machines with non-identical capacities. For the case of equal release times, we gave efficient exact algorithms for various objective functions. For the case of unequal release times, we gave efficient exact algorithms for minimizing makespan. The findings extend previous results for uniform machines counterparts.
Future research should focus on extending the algorithms to the case of unequal release times for objective functions other than makespan. It would also be interesting (and difficult) to extend the techniques to other related models, for general or special cases of processing set restrictions, such as scenario-dependent processing times and/or due dates [43], two-agent scheduling problems [44], or multitasking scheduling problems [45].
This work is supported by Natural Science Foundation of Shandong Province China (No. ZR2020MA030).
The authors declare there is no conflict of interest.
[1] | Andreoni J (1990) Impure Altruism and Donation to Public Goods: A Theory of Warm–Blow Giving. Econ J 100: 464–477. Available from: https://econweb.ucsd.edu/~jandreon/Publications/ej90.pdf |
[2] | Arrow KJ (1973) Social Responsibility and Economic Efficiency. Public Policy 21: 303–317. |
[3] | Baecker RM (2019) Computers and Society: Modern Perspectives. Oxford University Press, Oxford, UK. |
[4] | Cassiers I, Maréchal K, Méda ed D (2018) Post–growth Economics and Society: Exploring the Paths of a Social and Ecological Transition. Routledge, Abingdon, UK. |
[5] | Choudrie J, Tsatsou P, Kruria S (2018) Social Inclusion and Usability of ICT–Enable Services. Routledge, Abingdon, UK. |
[6] | Coase RH (1937) The characteristics of the Firm. Economica 4: 386–405. |
[7] | Global Sustainable investment Alliance (2013) Sustainable Investment Review 2012. Available from: https://apo.org.au/sites/default/files/resource-files/2013-01/apo-nid228346.pdf |
[8] | Global Sustainable Investment Alliance (2021) Global Sustainable Investment Review 2020. Available from: http://www.gsi-alliance.org/wp-content/uploads/2021/08/GSIR-20201.pdf |
[9] | Hindman M (2018) The Internet Trap: How the Digital Economy Builds Monopolies and Undermines Democracy. Princeton University Press, Princeton, USA. |
[10] | Mansell SF (2013) Capitalism, Corporation and the Social Contract: A Critique of Stakeholder Theory. Cambridge University Press, Cambridge, UK. |
[11] | Oskam JA (2019) The future of Airbnb and 'Sharing Economy': The Collaborative Consumption of our Cities. Channel View Publications, Bristol, UK. http://doi.org/10.21832/OSKAM/6737 |
[12] | Paus E ed (2018) Confronting Dystopia: The New Technological Revolution and the Future of Work. Cornel University Press, New York, USA. |
[13] | Pistor K (2019) The Code of Capital: How the Law Creates Wealth and Inequality, Princeton University, Princeton, USA. |
[14] | Richardson HW, Nam CW (2014) Shrinking Cities; A global perspective. Routledge, New York, USA. |
[15] | Rifkin J (2014) The Zero Marginal Cost Society: The internet of Things, The Collaborative Commons, and The Eclipse of Capitalism. St. Martin's Press, New York, USA. |
[16] |
Roberts RD (1984) A Positive Model of Private Charity and Public Transfer. J Polit Econ 92: 136–148. http://dx.doi.org/10.1086/261212 doi: 10.1086/261212
![]() |
[17] | Sciarelli M, Cosimato S, Landi G, et al. (2021) Socially responsible investment strategies for the transition towards sustainable development: The importance of integrating and communicating ESG. TQM J 33: 39–56. https://doi.org/10.1108/TQM–08–2020–0180 |
[18] | Tanaka H (2004) Kigyo no Syakaiteki Sekinin no Keizai Riron (Japanese; Theoretical Analysis for Corporate Social Responsibility). Chikyuu Kankyou Report (Japanese; Global Environmental Policy in Japan) 9: 1–9. |
[19] | Tanaka H (2016) The Sustainability Theorem in the ESG Mechanism. Long Financ London Accord, 1–29. Available from https://www.longfinance.net/programmes/sustainable–futures/london–accord/reports/the–sustainability–theorem–in–the–esg–mechanism/ |
[20] |
Tanaka H (2017) Sustainability of Global Communities and Regional Risk Governance. Asia Pac J Reg Sci 1: 639–653. http://doi.org/10.1007/s41685–017–0057–x doi: 10.1007/s41685–017–0057–x
![]() |
[21] |
Tanaka H (2018) Mechanism of Sustainability and Structure of Stakeholders in Regions. Financ Forum 7: 1–12. http://doi.org/10.18686/ff.v7i1 doi: 10.18686/ff.v7i1
![]() |
[22] | Tanaka H (2019a) Rehabilitation of the Decentralization in the Centralizing Process of Global Communities. J Global Issues Solutions 19: 1–18. Available from: https://www.bwwsociety.org/journal/current/2019/may-june/rehabilitation-of-the-decentralization-in-the-centralizing-process-of-global-communities.htm |
[23] |
Tanaka H (2019b) Innovation on the Digital Economies and Sustainability of the Global Communities. Ann Social Sci Manage Stud 4: 1–10. http://doi.org/10.1980/ASM.2019.04.555635 doi: 10.1980/ASM.2019.04.555635
![]() |
[24] |
Tanaka H (2019c) Sustainable Governance of Marine Stakeholders. Oceanogr Fish Open Access J 11: 1–4. http://doi.org/10.19080/OFOAJ.2019.11.555805 doi: 10.19080/OFOAJ.2019.11.555805
![]() |
[25] |
Tanaka H (2020a) Chinese sustainable framework in the digitalized global communities. Int J Econ Policy Stud 14: 327–336. http://doi.org/10.1007/s42495–020–00039–w doi: 10.1007/s42495–020–00039–w
![]() |
[26] | Tanaka H (2020b) Digital Revolution and Structural Reform of Stakeholders. J Global Issues Solutions 20: 1–7. Available from: https://bwwsociety.org/journal/current/2020/jan-feb/digital-reform-and-structural-reform-of-stakeholders.htm |
[27] |
Tanaka H (2020c) Digital Economic and Social Systems to be Featured by Stakeholders. Ann Social Sci Manage Stud 5: 128–136. http://doi.org/10.1980/ASM.2020.05.555670 doi: 10.1980/ASM.2020.05.555670
![]() |
[28] | Tanaka H (2021a) Green Bonds Issuance and Chinese Sustainable Governance. Long Financ London Accord 1–16. Available from https://www.longfinance.net/media/documents/Green_bonds_and_Chinese__Sustainable_Governance_.pdf; Accessed, 23 March, 2022. |
[29] |
Tanaka H (2021b) Digital Industrial Revolution and an Index of Transaction Cost. Am J Novel Res Sci 8: 1–2. http://doi.org/10.31031/NRS.2021.08.000678 doi: 10.31031/NRS.2021.08.000678
![]() |
[30] |
Tanaka H, Tanaka C (2021c) Green Bonds Issuance and Stakeholders Governance. Ann Social Sci Manage Stud 6: 1–11. http://doi.org/10.1980/ASM.2021.06.555697 doi: 10.1980/ASM.2021.06.555697
![]() |
[31] | Tanaka H (2022) Sustainable provision of medical services with radiation in digital industrial revolution, Ann Radiol Med Imaging 1: 1–8. Available from: http://scientificeminencegroup.com/articles/Sustainable-Provision-of-Medical.pdf |
[32] | Tirole J (2001) Corporate Governance. Econometrica 68: 1–35. |
[33] | Williamson OE (1975) Markets and Hierarchies: Analysis and Antitrust Implication. The Free Press. |
[34] | Williamson OE (1986) Economic Organization: Firms, Markets and Policy Control. Wheatsheaf Books, Brighton, UK. |
[35] | Williamson OE (ed) (1990) Industrial Organization. Edward Elgar Publishing, Cheltenham, UK. |
[36] | UNEP FI, Compact UNG (2012) Responsible Investment and Hedge Funds: A Discussion paper. Available from: https://www.unpri.org/download?ac=4155 |
1. | Naveed Iqbal, Mohammad Alshammari, Wajaree Weera, Numerical analysis of fractional-order nonlinear Gardner and Cahn-Hilliard equations, 2022, 8, 2473-6988, 5574, 10.3934/math.2023281 | |
2. | Fatemeh Nejati, Wahidullah Omer Zoy, Nayer Tahoori, Pardayev Abdunabi Xalikovich, Mohammad Amin Sharifian, Moncef L. Nehdi, Machine Learning Method Based on Symbiotic Organism Search Algorithm for Thermal Load Prediction in Buildings, 2023, 13, 2075-5309, 727, 10.3390/buildings13030727 | |
3. | Ling Li, Yongxian Li, Firdous A. Shah, Structure Preprocessing Method for the System of Unclosed Linear Algebraic Equations, 2022, 2022, 2314-4785, 1, 10.1155/2022/5435076 | |
4. | Muhammad Naeem, Humaira Yasmin, Rasool Shah, Nehad Ali Shah, Kamsing Nonlaopon, Investigation of Fractional Nonlinear Regularized Long-Wave Models via Novel Techniques, 2023, 15, 2073-8994, 220, 10.3390/sym15010220 | |
5. | Xiaoming You, Gongxing Yan, Murtadha M. Al-Masoudy, Mohamed Amine Kadimallah, Tamim Alkhalifah, Fahad Alturise, H. Elhosiny Ali, Application of novel hybrid machine learning approach for estimation of ultimate bond strength between ultra-high performance concrete and reinforced bar, 2023, 180, 09659978, 103442, 10.1016/j.advengsoft.2023.103442 | |
6. | Ruyi Dong, Junjie Du, Yanan Liu, Ali Asghar Heidari, Huiling Chen, An enhanced deep deterministic policy gradient algorithm for intelligent control of robotic arms, 2023, 17, 1662-5196, 10.3389/fninf.2023.1096053 | |
7. | Xiao Xin, Muhammad Ijaz Khan, Shuguang Li, Scheduling equal-length jobs with arbitrary sizes on uniform parallel batch machines, 2023, 21, 2391-5455, 10.1515/math-2022-0562 | |
8. | Rezgar Hasanzadeh, Rzgar M. Abdalrahman, A Regression Analysis on Steam Gasification of Polyvinyl Chloride Waste for an Efficient and Environmentally Sustainable Process, 2023, 15, 2073-4360, 2767, 10.3390/polym15132767 | |
9. | Ifeyinwa Jacinta Onu, Abiodun Esther Omolara, Moatsum Alawida, Oludare Isaac Abiodun, Abdulatif Alabdultif, Detection of Ponzi scheme on Ethereum using machine learning algorithms, 2023, 13, 2045-2322, 10.1038/s41598-023-45275-0 | |
10. | Lal Mohammad, Jatisankar Bandyopadhyay, Rubel Sk, Ismail Mondal, Trinh Trong Nguyen, Giuseppe Francesco Cesare Lama, Duong Tran Anh, Estimation of agricultural burned affected area using NDVI and dNBR satellite-based empirical models, 2023, 343, 03014797, 118226, 10.1016/j.jenvman.2023.118226 | |
11. | Ya Qin, Rizk M. Rizk-Allah, Harish Garg, Aboul Ella Hassanien, Václav Snášel, Intuitionistic fuzzy-based TOPSIS method for multi-criterion optimization problem: a novel compromise methodology, 2023, 8, 2473-6988, 16825, 10.3934/math.2023860 | |
12. | Dongze He, Qingshan Wang, Rui Zhong, Bin Qin, A unified spectral-geometric model of FGM double conical/cylindrical/spherical shell coupled with annular plates, 2023, 143, 08981221, 348, 10.1016/j.camwa.2023.05.001 | |
13. | Helong Yu, Zisong Zhao, Jing Zhou, Ali Asghar Heidari, Huiling Chen, Sine cosine algorithm with communication and quality enhancement: Performance design for engineering problems, 2023, 10, 2288-5048, 1868, 10.1093/jcde/qwad073 | |
14. | Atef El Jery, Moutaz Aldrdery, Ujwal Ramesh Shirode, Juan Carlos Orosco Gavilán, Abubakr Elkhaleefa, Mika Sillanpää, Saad Sh. Sammen, Hussam H. Tizkam, An Efficient Investigation and Machine Learning-Based Prediction of Decolorization of Wastewater by Using Zeolite Catalyst in Electro-Fenton Reaction, 2023, 13, 2073-4344, 1085, 10.3390/catal13071085 | |
15. | Deming Lei, Tao Dai, An adaptive shuffled frog-leaping algorithm for parallel batch processing machines scheduling with machine eligibility in fabric dyeing process, 2024, 62, 0020-7543, 7704, 10.1080/00207543.2024.2324452 | |
16. | Leren Qian, Jiexin Bai, Yiqian Huang, Diyar Qader Zeebaree, Abbas Saffari, Dilovan Asaad Zebari, Breast cancer diagnosis using evolving deep convolutional neural network based on hybrid extreme learning machine technique and improved chimp optimization algorithm, 2024, 87, 17468094, 105492, 10.1016/j.bspc.2023.105492 | |
17. | Chunlei Lin, Junhui Zhou, Qianqian Lu, Mohamad Khaje Khabaz, Amirreza Karimi Andani, Mortatha Al-Yasiri, Guangyong Pan, Thermal conductivity prediction of WO3-CuO-Ag (35:40:25)/water hybrid ternary nanofluid with Artificial Neural Network and back-propagation algorithm, 2023, 36, 23524928, 106807, 10.1016/j.mtcomm.2023.106807 | |
18. | Mohana Alanazi, Abdulmajeed Alanazi, Kareem M. AboRas, Yazeed Yasin Ghadi, Olubayo Babatunde, Multiobjective and Coordinated Reconfiguration and Allocation of Photovoltaic Energy Resources in Distribution Networks Using Improved Clouded Leopard Optimization Algorithm, 2024, 2024, 1099-114X, 1, 10.1155/2024/7792658 | |
19. | Wei Tang, Shuili Yang, Mohammad Khishe, Profit prediction optimization using financial accounting information system by optimized DLSTM, 2023, 9, 24058440, e19431, 10.1016/j.heliyon.2023.e19431 | |
20. | Yanyue Liang, Lihong Zhang, Shuguang Li, 2024, Fast approximation algorithms for scheduling uniform parallel batch machines with inclusive processing set restriction, 979-8-3503-6144-5, 70, 10.1109/ICAACE61206.2024.10548968 | |
21. | Fengxian Wang, Shaozhi Feng, Youmei Pan, Huanlong Zhang, Senlin Bi, Jiaxiang Zhang, Dynamic spiral updating whale optimization algorithm for solving optimal power flow problem, 2023, 79, 0920-8542, 19959, 10.1007/s11227-023-05427-5 | |
22. | Daniel Constantin Diaconu, Romulus Costache, Abu Reza Md. Towfiqul Islam, Manish Pandey, Subodh Chandra Pal, Arun Pratap Mishra, Chaitanya Baliram Pande, Developing flood mapping procedure through optimized machine learning techniques. Case study: Prahova river basin, Romania, 2024, 54, 22145818, 101892, 10.1016/j.ejrh.2024.101892 | |
23. | Hamed Karimian, Jinhuang Huang, Youliang Chen, Zhaoru Wang, Jinsong Huang, A novel framework to predict chlorophyll-a concentrations in water bodies through multi-source big data and machine learning algorithms, 2023, 30, 1614-7499, 79402, 10.1007/s11356-023-27886-2 | |
24. | Haitham A. Mahmoud, Azhar Imran, Ch Anwar Ul Hassan, Mohammed A. El-Meligy, Optimizing Accounting Information Systems With Hybrid Capsule Network and Honey Badger Particle Swarm Optimization, 2024, 12, 2169-3536, 153346, 10.1109/ACCESS.2024.3481034 |