extended Abstracts The first international workshop on dynamic scheduling problems ADAM MICKIEWICZ UNIVERSITY IN POZNAŃ Faculty of Mathematics and Computer Science June 30th – July 1st, 2016, PoznaŃ, POLAND PoznaŃ 2016 extended Abstracts The first international workshop on dynamic scheduling problems ADAM MICKIEWICZ UNIVERSITY IN POZNAŃ Faculty of Mathematics and Computer Science June 30th – July 1st, 2016, PoznaŃ, POLAND PoznaŃ 2016 This book contains extended abstracts of a plenary lecture and papers presented at the First International Workshop on Dynamic Scheduling Problems, June 30th– July 1st, 2016, Poznań, Poland. © 2016 by the Polish Mathematical Society and the Authors This work is subject to copyright. All rights reserved. Layout, maps and cover design by Bartłomiej Przybylski Edited by Stanisław Gawiejnowicz ISBN: 978-83-937220-7-5 (eBook) Publisher: Polish Mathematical Society Śniadeckich 8, 00-956 Warsaw Poland Welcome to IWDSP 2016 Dear participants, on behalf of the Programme and Local Committees, I am pleased to welcome you to IWDSP 2016,The First International Workshop on Dynamic Scheduling Prob- lems, and to the Faculty ofMathematics andComputer Science, AdamMickiewicz University in Poznań, which is the host of the event. This workshop is focused on dynamic scheduling problems defined by parame- ters whose values are varying in time. Problems of this kind appear in many applications, the most common examples are scheduling problems with time-, position- and resource-dependent job processing times. The aim of IWDSP 2016 is to present recent research in this important domain of scheduling theory. The Programme Committee, supported by the members of Advisory Committee and external reviewers, selected for presentation at IWDSP 2016 talks submitted by the authors fromAustralia, Belarus, Canada, China, France, Israel, Poland, Rus- sian Federation, Taiwan and United Kingdom. The quality of these talks allowed to prepare an attractive scientific programme of IWDSP 2016. I wish you all the pleasant stay in Poznań and an enjoyable workshop, expressing the hope that you will find IWDSP 2016 stimulating for your further research. Stanisław Gawiejnowicz The Chair of the Programme Committee The Chair of the Local Committee 3 Committees Programme Committee StanisławGAWIEJNOWICZ (chair),AdamMickiewiczUniversity in Poznań, Poland Gur MOSHEIOV, Hebrew University, Jerusalem, Israel Vitaly A. STRUSEVICH, Greenwich University, London, United Kingdom Advisory Committee Florian JAEHN, University of Augsburg, Augsburg, Germany AlexanderKONONOV, Sobolev Institute ofMathematics, Novosibirsk, Russian Federation Mikhail Y. KOVALYOV, National Academy of Sciences of Belarus, Minsk, Belarus Bertrand M-T. LIN, National Chiao Tung University, Hsinchu, Taiwan Dvir SHABTAY, Ben-Gurion University of the Negev, Beer Sheva, Israel Natalia SHAKHLEVICH, University of Leeds, Leeds, United Kingdom Ji-Bo WANG, Shenyang Aerospace University, Shenyang, People’s Republic of China Local Committee Stanisław GAWIEJNOWICZ (chair), AdamMickiewicz University in Poznań Jan KACZMAREK, AdamMickiewicz University in Poznań Zbigniew PALKA, AdamMickiewicz University in Poznań Bartłomiej PRZYBYLSKI, AdamMickiewicz University in Poznań Cezary SUWALSKI, AdamMickiewicz University in Poznań Marcin ŻUROWSKI, AdamMickiewicz University in Poznań 7 Contents Welcome to IWDSP 2016 3 Committees 7 Venue 13 Programme 19 Plenary lecture 23 Approximation algorithms for scheduling under uncertainty Marc Uetz 23 Extended abstracts 29 Scheduling data gathering with variable communication speed Joanna Berlińska 29 Solving a time-dependent scheduling problem by interior point method Stanisław Gawiejnowicz, Wiesław Kurc 33 Minmax scheduling with acceptable lead-times: Extensions to position- dependent processing times, due-window and job rejection Enrique Gerstl, Baruch Mor, Gur Mosheiov 37 An ”almost-exact” solution to speed scaling scheduling of parallel jobs with preemption Alexander Kononov, Yulia Kovalenko 41 Workforce planning for cyclic production of multiple parts Mikhail Y. Kovalyov, Xavier Delorme, Alexandre Dolgui 45 9 10 The First International Workshop on Dynamic Scheduling Problems Directed sets, Möbius inversing formula and time-dependent scheduling on precedence-constrained machines Wiesław Kurc, Stanisław Gawiejnowicz 49 Relocation scheduling with optional recycling operations Bertrand M-T. Lin 53 Financial scheduling with time-dependent resource consumption Krzysztof M. Ocetkiewicz, Michał Małafiejski 57 Scheduling on identical parallel machines with controllable processing times to minimize the makespan Daniel Oron, Dvir Shabtay, George Steiner 61 Precedence constrained position-dependent scheduling on parallel machines via schedule transformations Bartłomiej Przybylski 65 Single machine scheduling subject to a generalized linear cumulative effect Kabir Rustogi, Vitaly A. Strusevich 69 An approach for proving the NP-hardness of optimization problems with hard computable objectives Yakov M. Shafransky, T-C. Edwin Cheng, C-T. Daniel Ng 73 Indexes 79 Venue Location IWDSP 2016 takes place at the Faculty of Mathematics and Computer Science, AdamMickiewicz University in Poznań, Umultowska 87, 61-614 Poznań. The faculty is located in a new part of Adam Mickiewicz University in Poznań, called Morasko campus (for details see attached map). Communication The quickest way to reach the venue of IWDSP 2016 is to take tram no. 12, 14 or 16 of Poznań Rapid Tram, get off at final stop (’Os. Sobieskiego’, for timetable see www.mpk.poznan.pl) and make a short walk to the Morasko campus (for suggested route see attached map). Registration Registration desk for IWDSP 2016 will be located in the main hall of the Faculty of the Mathematics and Computer Science. Registration will be possible on Wednesday, June 29th at evening, and on Thurs- day, June 30th at morning. Presentation room Plenary lecture and all presentations during IWDSP 2016 will take place in the Faculty Council Room (A1-33, see the attached map). The room is equipped with a computer projector for handling presentations in typical formats such as PDF or PPT. Coffee breaks room Coffee breaks will take place in Professors’ Club (A0-13) that is located one floor below the Faculty Council Room (for details see attached map). Internet access Wireless network is available in the building of the Faculty of Mathematics and Computer Science. Details concerning usernames and passwords will be given during registration. 13 Welcome party, lunches and conference dinner On Wednesday, June 29th in the afternoon, in Professors’ Club of the Faculty of Mathematics and Computer Science there will be organized Welcome Party. Lunches at June 30th and July 1st will be served in Professors’ Club. Conference dinner will be organized outside the Morasko campus. Details con- cerning the dinner will be given during registration. Social programme On Friday, July 1st in the morning, there will be organized a walking guided tour including the main tourist attractions of Poznań. 14 The First International Workshop on Dynamic Scheduling Problems June 30 – July 1, 2016, Poznań, Poland 15 Figure 1: The main part of Morasko campus (source: Open Street Map) 16 The First International Workshop on Dynamic Scheduling Problems Faculty Council Room A1-33 Block B Library Entry B Entry A Computer Laboratories to level 0 Lecture halls Lecture halls ToiletsMain hall Figure 2: Level 1 (ground floor) of IWDSP 2016 venue Professors' Club A0-13 Block B Lecture halls Canteen to level 1 Toilets Figure 3: Level 0 (basement) of IWDSP 2016 venue Programme Thursday, June 30th, 2016 08:00 – 08:30 Registration 08:30 – 09:00 Opening 09:00 – 10:20 Session no. 1 Speakers: Yakov M. Shafransky, Gur Mosheiov Chair: Vitaly A. Strusevich 10:20 – 10:40 Coffee break 10:40 – 12:00 Plenary lecture Speaker: Marc Uetz Chair: Stanisław Gawiejnowicz 12:00 – 13:30 Lunch break 13:30 – 14:50 Session no. 2 Speakers: Bartłomiej Przybylski, Vitaly A. Strusevich Chair: Mikhail Y. Kovalyov 14:50 – 15:10 Coffee break 15:10 – 16:30 Session no. 3 Speakers: Stanisław Gawiejnowicz, Alexander Kononov Chair: Gur Mosheiov 16:30 – 16:50 Coffee break 19:30 – 22:00 Conference dinner Friday, July 1st, 2016 08:00 – 12:00 Guided tour 12:00 – 13:30 Lunch break 13:30 – 14:50 Session no. 4 Speakers: Dvir Shabtay, Wiesław Kurc Chair: Alexander Kononov 14:50 – 15:10 Coffee break 15:10 – 16:30 Session no. 5 Speakers: Mikhail Y. Kovalyov, Joanna Berlińska Chair: Dvir Shabtay 16:30 – 16:50 Coffee break 16:50 – 18:10 Session no. 6 Speakers: Bertrand M-T. Lin, Krzysztof M. Ocetkiewicz Chair: Stanisław Gawiejnowicz 18:10 Closing 19 Plenary lecture Approximation algorithms for scheduling under uncertainty Marc Uetz* University of Twente, Enschede, The Netherlands Keywords: stochastic scheduling, approximation algorithms, linear programming 1 Introduction We address machine scheduling problems with stochastic processing times, when the objective is to minimize the expected value of the total weighted completion time. We give an overview of LP-based scheduling policies with provable perfor- mance guarantees. The obtained performance bounds depend linearly on the squared coefficient of the variation of underlying processing time distributions. We are focused on the problem to minimize the total weighted completion time on identical parallel machines, denoted P | | ∑ wjCj in the three-field notation of Graham et al. [4], or on unrelated parallel machines, denoted R | | ∑ wjCj. Both problems are among the most-studied problems in the theory of schedul- ing. The former is stronglyNP-hard [8] and admits a PTAS [1], while the latter is MaxSNP-hard [6], and a 3 2 -approximation algorithm is known for it, e.g. [2]. We here address the variant where the processing times of jobs are random vari- ables. The solution is then no longer a schedule, but a more complicated object called non-anticipatory scheduling policy [9]. Roughly speaking, for any state that the system might be in, a policy prescribes which job is to be scheduled next. For a given scheduling policy, the objective function ∑ j wjCj is then a random vari- able, too, and our goal is to minimize its expected value, which by linearity of expectation equals ∑ j wjE[Cj]. The problem under consideration is defined as follows. We are given a set of jobs J of cardinality n with job weights wj ∈ Z>0, and a set of identical or unrelated par- allel machines M of cardinality m. Moreover, we are given a random variable Pij that describes the possible outcomes for job j’s processing time on machine i, for every job j ∈ J and every machine i ∈ M. For the special case with identical par- allel machines, Pj denotes the random variable for job j’s processing time. Each job j needs to be executed on any one of the machines i ∈ M, and each machine can process at most one job at a time. The random variables Pij and Pj are stochas- tically independent across jobs. * Plenary speaker, email: m.uetz@utwente.nl 23 2 Performance guarantees We can compute, in polynomial time, scheduling policies with provable expected performance bymeans ofLP relaxations. The basic idea is first to solve a certain LP relaxation, then derive from its solution a scheduling policy, and finally compare its expected performance with that of the relaxation. As the LP relaxation lower bounds the expected performance of any scheduling policy, this yields the desired performance guarantee. The following table summarizes our (multiplicative) performance bounds for the two problems with identical and unrelated machines, respectively. Here, ε > 0 can be chosen arbitrarily small, and parameter Δ upper bounds the squared co- efficient of variation CV2[Pij] = Var[Pij] E2[Pij] for all Pij. The third column shows the results for uniform and exponential distributions for CV[Pij] ≤ 1. Stochastic scheduling Worst-case performance guarantee Reference problem Arbitrary Pij CV[Pij] ≤ 1 P | |E [∑ wjCj ] 3 2 + Δ 2 − Δ+1 2m 2− 1 m [10] R | |E [∑ wjCj ] 3 2 + Δ 2 + ε 2+ ε [12] 3 Techniques for relaxations and scheduling policies The LP relaxation for the problem with identical parallel machines simply uses variables CLP j to denote the LP completion time of job j. It can be shown that the following is a valid LP relaxation: min ∑ j∈J wj CLP j s.t. ∑ j∈W E[Pj]CLP j ≥ f(W) , for allW ⊆ J, where f(W) := 1 2m (∑ j∈W E[Pj] )2 + 1 2 ∑ j∈W E[Pj]2 − ( 1 2 − 1 2m )∑ j∈WVar[Pj]. These inequalities, for the special case of deterministic processing times where Var[Pj] = 0, have been used also before [5]. This LP is a polymatroid, and there- fore its optimal solution can be computed combinatorially using Edmonds’ greedy algorithm [3]. The scheduling policy that achieves the performance bound 3 2 + Δ 2 − Δ+1 2m is the stochastic variant of Smith’s rule: greedily schedule the jobs in order of non-increasing ratios wj E[Pj] . 24 The First International Workshop on Dynamic Scheduling Problems For the problem with unrelated machines, we use a time-indexed LP relaxation, based on variables xijt that denote the probability to start job j on machine i at time t. Using these variables, a valid LP relaxation for the problem is as follows: min ∑ j∈J wj CLP j s.t. ∑ i∈M ∑ t∈Z≥0 xijt = 1 for all j ∈ J,∑ j∈J ∑s t=0 xijt qij s−t ≤ 1 for all i ∈ M, s ∈ Z≥0, CLP j = ∑ i∈M ∑ t∈Z≥0 xijt (t+ E[Pij]) for all j ∈ J, xijt ≥ 0 for all j ∈ J, i ∈ M, t ∈ Z≥0. Note that the variables CLP j are completely determined by xijt and only included for convenience. We can show that one can solve this LP with arbitrary precision in polynomial time. The algorithm to translate the LP solution into a scheduling policy is to assign job j to machine i at random, namely with probability ∑ t xijt. The jobs assigned to a given machine i are then again sequenced as in Smith’s rule. That policy achieves the performance bound of 3 2 + Δ 2 + ε. 4 Concluding remarks Our results can also be generalized to include problems, where jobs have indi- vidual release dates rj. Then, the LPs are simply augmented with release dates, i.e. CLP j ≥ rj, and also for identical parallel machines the scheduling policy is no longer Smith’s rule, but we schedule the jobs in order of non-decreasing LP completion times CLP j . The performance bounds are equal to 2 + Δ for identical parallel machines [11] and to 2+ Δ+ ε for unrelated machines [12]. It can also be shown that the dependence of the performance bounds on the squared coefficient of variation is asymptotically tight. The most intriguing open problem is to get rid of the dependence of the performance bounds on the coef- ficient of variation Δ, and obtain constant bounds for arbitrary processing time distributions. Some progress in that direction has very recently been obtained [7]. References [1] F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, M. Sviridenko, Approximation schemes for minimizing average weighted completion time with release dates, The 40th Annual IEEE Symposium on Foundations of Computer Sci- ence, IEEE, 1999, pp. 32–43. June 30 – July 1, 2016, Poznań, Poland 25 [2] F. A. Chudak, A min-sum 3 2 -approximation algorithm for scheduling unre- lated parallel machines, Journal of Scheduling, 2 (1999), 73–77. [3] J. Edmonds, Submodular functions, matroids and certain polyhedra, Pro- ceedings of the International Conference on Combinatorics, Gordon and Breach, 1970, pp. 69–87. [4] R. L. Graham, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, Optimiza- tion and approximation in deterministic sequencing and scheduling: A sur- vey, Annals of Discrete Mathematics, 5 (1979), 287–326. [5] L. A. Hall, A. S. Schulz, D. B. Shmoys, J. Wein, Scheduling to minimize average completion time: Off-line and on-line approximation algorithms, Mathematics of Operations Research, 22 (1997), 513–544. [6] H. Hoogeveen, P. Schuurman, G. J. Woeginger, Non-approximability re- sults for scheduling problems with minsum criteria, INFORMS Journal on Computing, 13 (2001), 157–168. [7] S. Im, B. Moseley, K. Pruhs, Stochastic scheduling of heavy-tailed jobs, The 32nd Symposium on Theoretical Aspects of Computer Science, Leibniz Inter- national Proceedings in Informatics, 30 (2015), pp. 474–486. [8] J. K. Lenstra, A. H. G. Rinnooy Kan, P. Brucker, Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1 (1977), 343–362. [9] R. H. Möhring, F. J. Radermacher, G. Weiss, Stochastic scheduling prob- lems I: General strategies, ZOR — Zeitschrift für Operations Research, 28 (1984), 193–260. [10] R. H. Möhring, A. S. Schulz, M. Uetz, Approximation in stochastic schedul- ing: The power of LP-based priority policies, Journal of the ACM, 46 (1999), 924–942. [11] A. S. Schulz, Stochastic online scheduling revisited, The 2nd Conference on Combinatorial Optimization and Applications, Lecture Notes in Computer Science, 5165 (2008), pp. 448–457. [12] M. Skutella, M. Sviridenko, M. Uetz, Unrelated machine scheduling with stochastic processing times, Mathematics of Operations Research, to appear, DOI: 10.1287/moor.2015.0757, 2016. 26 The First International Workshop on Dynamic Scheduling Problems Extended abstracts Scheduling data gathering with variable communication speed Joanna Berlińska* AdamMickiewicz University in Poznań, Poznań, Poland Keywords: scheduling, data gathering networks, variable communication speed 1 Introduction Gathering data from remote processors is an important stage of many applica- tions. Running computations in distributed systems requires collecting results obtained by many workers. Wireless sensor networks collecting data find envi- ronmental, military, health and home applications [1]. Specific communication protocols have been designed for wireless sensor networks to increase data gath- ering efficiency [5, 6, 9]. General scheduling algorithms for data gathering were proposed in [2, 3, 4, 7]. It was assumed in these papers that the network parame- ters, such as the speed of communication and processing, are constant. However, in reality the communication speed often changes because of sharing communi- cation links with other users, maintenance activities etc. Hence, in this work we study scheduling for data gathering networks with variable communication speed. 2 Problem formulation We analyze a star network consisting ofm nodes P1, P2, . . . , Pm and a single base station. Node Pi has to transfer data of size αi directly to the base station, possibly inmany separatemessages. Only one node can communicatewith the base station at a time. We assume the linear model of communication, i.e., communication capabilities of node Pi are characterized by a single parameter called communica- tion rate (inverse of speed). Thus, if node Pi communicates with rate C, then it transfers data of size x in time Cx. According to the methodology of divisible load theory [8], we assume that data size x is a rational number. It is assumed that the communication rate of a link between node Pi and the base station changes in negligible time, when another application starts using it, and then remains constant for some period of time. In other words, it is a piecewise constant function of time. Let t0 = 0 be the time when data gathering starts. The communication rates change at nmoments tj > 0, 1 ≤ j ≤ n, t1 < t2 < · · · < tn * Speaker, email: Joanna.Berlinska@amu.edu.pl 29 and tn+1 = ∞. The communication rate of node Pi in interval [tj, tj+1) will be denoted by Ci,j for j = 0, 1, . . . , n. Problem DG-VS (scheduling data gathering with variable communication speed) consists in scheduling the communications between the nodes P1, P2, . . . , Pm and the base station so that the whole data is transferred in the shortest possible timeT. 3 Offline algorithm Theorem 1. The offline version of DG-VS can be solved in polynomial time. Proof. Suppose that T ∈ [tk, tk+1) for given k ∈ {0, 1, . . . , n}. Then, T can be found by solving the following linear program: minimize T (1) k∑ j=0 xi,j = αi for i = 1, 2, . . . ,m (2) m∑ i=1 Ci,jxi,j ≤ tj+1 − tj for j = 0, 1, . . . , k− 1 (3) m∑ i=1 Ci,kxi,k ≤ T− tk (4) In the above program, xi,j (1 ≤ i ≤ m, 0 ≤ j ≤ k) are rational variables repre- senting the amount of data sent by node Pi in interval [tj, tj+1). We minimize the data gathering completion time T. By constraints (2) each node transfers all its data to the base station. Inequalities (3) and (4) guarantee that the communica- tions fit in the time intervals where they are assigned. Linear program (1)-(4) has m(k + 1) + 1 = O(mn) variables and m + k + 1 = O(m + n) constraints, and hence it can be solved in polynomial time. In order to solve DG-VS one can use binary search to find the smallest k for which program (1)-(4) has a solution. The number of binary search iterations isO(log n). The optimum communication schedule can be obtained from the values of vari- ables xi,j. Namely, in each interval [tj, tj+1) we schedule consecutively commu- nications from nodes P1, P2, . . . , Pm of sizes x1,j, x2,j, . . . , xm,j correspondingly, starting at time tj. Thus, problem DG-VS can be solved in polynomial time. 30 The First International Workshop on Dynamic Scheduling Problems 4 Online algorithm Let us assume that although we do not know the exact ranges of communica- tion speeds changes, the relative range of communication rate changes is known. Namely, if Cmax i and Cmin i are the maximum and the minimum communication rate of node Pi, then Cmax i Cmin i ≤ Δ for some given Δ > 1. Such a situation may arise, e.g., when using a network with QoS Percentage-Based Policing [10]. Observation 1. Any online scheduling strategy for DG-VSwhich does not introduce idle times in communication is Δ-competitive, since no communication can be more than Δ times slower than in the optimum schedule. Observation 2. If no additional information is given, no online algorithmA consist- ing in reacting to changing communication speeds can be better than Δ-competitive. Proof. Let m = 2, α1 = α2 = 1, C1,0 = C2,0 = 1. We can assume without loss of generality that the first sender chosen by algorithm A is P1. Now, let t1 = 1, C1,1 = 1 Δ , C2,1 = Δ. The schedule length T = 1+Δ obtained by algorithm A is Δ times larger than the optimum schedule length T∗ = 1+ 1 Δ . Since byObservations 1 and 2 it is not possible to construct a better than trivial on- line algorithm without additional knowledge, let us now assume that the network is homogeneous, i.e. αi = α, Cmin i = Cmin and Cmax i = Cmax for all i. Theorem2. There exists a 1+(m−1)Δ2 1+(m−1)Δ -competitive online algorithm solving problem DG-VS for a homogeneous network. Proof. Consider algorithm A that always chooses as the sender the node with the smallest current communication rate. Let S denote the schedule of length T con- structed by A and let S∗ be the optimum schedule of length T∗. Let Pi be the last sender in schedule S . The total length of intervals when Pi transfers data in schedule S∗ will be denoted by T∗ i . Let T∗ other = T∗−T∗ i . Note that it is possible to send data from Pi in schedule S , whenever Pi sends data in schedule S∗. Hence, in the corresponding time intervals the communication in S is not slower than in S∗ and the size of sent data is at least α. The remaining data, of size at most (m− 1)α, are sent in S in time at most ΔT∗ other. Thus, T ≤ T∗ i + ΔT∗ other. (5) Furthermore, we have T∗ other ≤ (m − 1)ΔT∗ i , and since T∗ i + T∗ other = T∗, we get T∗ other ≤ T∗(m−1)Δ 1+(m−1)Δ .Hence, we obtain from (5) that T T∗ ≤ 1+(m−1)Δ2 1+(m−1)Δ . June 30 – July 1, 2016, Poznań, Poland 31 5 Future research In this work, we analyzed minimizing data gathering time in a network with vari- able communication speed. We proposed a polynomial-time offline algorithm solving problem DG-VS and a 1+(m−1)Δ2 1+(m−1)Δ -competitive polynomial-time online al- gorithm solvingDG-VS in a homogeneous network. Future researchmay concern the construction of non-deterministic online algorithms for DG-VS. References [1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, Wireless sensor networks: A survey, Computer Networks, 38 (2002), 393–422. [2] J. Berlińska, Communication scheduling in data gathering networks with limited memory, Applied Mathematics and Computation, 235 (2014), 530–537. [3] J. Berlińska, Scheduling for data gathering networks with data compression, European Journal of Operational Research, 246 (2015), 744–749. [4] K. Choi, T. G. Robertazzi, Divisible load scheduling in wireless sensor net- works with information utility, IEEE International Performance Computing and Communications Conference 2008, IEEE, 2008, pp. 9–17. [5] S. C. Ergen, P. Varaiya, TDMA scheduling algorithms for wireless sensor networks,Wireless Networks, 16 (2010), 985–997. [6] S. Kumar, S. Chauhan, A survey on scheduling algorithms forwireless sensor networks, International Journal of Computer Applications, 20 (2011), 7–13. [7] M. Moges, T. G. Robertazzi, Wireless sensor networks: scheduling for mea- surement and data reporting, IEEE Transactions on Aerospace and Electronic Systems, 42 (2006), 327–340. [8] T. G. Robertazzi, Ten reasons to use divisible load theory, IEEE Computer, 36 (2003), 63–68. [9] L. Shi, A. Fapojuwo, TDMAschedulingwith optimized energy efficiency and minimum delay in clustered wireless sensor networks, IEEE Transactions on Mobile Computing, 9 (2010), 927–940. [10] T. Szigeti, C. Hattingh, R. Barton, K. Briley, End-to-EndQoSNetwork Design: Quality of Service for Rich-Media & Cloud Networks, Cisco Press, 2013. 32 The First International Workshop on Dynamic Scheduling Problems Solving a time-dependent scheduling problem by interior point method Stanisław Gawiejnowicz* AdamMickiewicz University in Poznań, Poznań, Poland Wiesław Kurc AdamMickiewicz University in Poznań, Poznań, Poland Keywords: single machine, time-dependent scheduling, total completion time, interior point method 1 Introduction In many applications one cannot assume that job processing times are known in advance and fixed. Therefore, in modern scheduling theory an important class of scheduling problems compose those with variable job processing times. One of forms of variable processing times is the one in which job processing times are time-dependent, i.e. depend on when the jobs start, [1]. In this talk, we consider a single-machine scheduling problem with time-dependent job processing times that are non-decreasing functions of the job starting times. For this problem, we propose a new algorithm based on interior point method, [6]. 2 Problem formulation The problem under consideration can be formulated as follows. A set of jobs J0, J1, . . . , Jn has to be processed on a single machine. All jobs are independent, non-preemptable and ready for processing at time 0.The processing time pj of Jj linearly deteriorates in time, i.e. pj = 1 + αjt, where deterioration rate αj > 0 and the job starting time t ≥ 0 for 0 ≤ j ≤ n. The aim is to find a schedule with minimal total completion time, ∑n j=1 C[j], whereC[j] denotes the completion time of the jth job in the schedule. In short, we will call this problem as problem (P). Notice that any instance of problem (P)may be identified with sequence of job de- terioration rates α0 = (α0, α1, . . . , αn) which, in turn, corresponds to a schedule for the problem. Thus, any permutation α = (α[0], α[1], . . . , α[n]) of α0 may also be identified with a schedule for (P). Therefore, we will use the same symbol for denoting a permutation of a given sequence of deterioration rates and a schedule corresponding to the sequence. * Speaker, email: stgawiej@amu.edu.pl 33 Given α, we can compute job completion times in the schedule corresponding to this α as follows: C[0] = 1, C[j] = C[j−1] + p[j](C[j−1]) = 1+ a[j]C[j−1] for 1 ≤ j ≤ n, where a[j] = 1+ α[j]. Hence, if we denote the sequence of aj’s corresponding to a given α0 by a0 = (a0, a1, . . . , an), any schedule for (P) may be identified with a permutation a from the set Perm(a0) of all permutations of a0. (Since further con- siderations are limited only to elements of Perm(a0), we will omit square brackets in indices and write j instead of [j].) 3 Related research Problem (P) has been introduced in [8], where three basic properties of optimal schedules for (P) have been shown. The maximum job property says that in any optimal schedule for (P) as the first job is scheduled the job with the maximal deterioration rate. The symmetry property says that optimal schedules for (P) are symmetric starting from the second position, i.e. if (α0, α1, . . . , αn) is an optimal schedule, then (α0, αn, . . . , α1) is optimal as well. Finally, the V-shape property states that if α is an optimal schedule for problem (P), then for some 0 ≤ m ≤ n it is non-increasing for 0 ≤ j ≤ m and non-decreasing form ≤ j ≤ n. The time complexity of problem (P) is still unknown. We conjecture that it is NP-hard in the ordinary sense. Properties presented in [8] decrease the number of possibly optimal schedules for (P) from O(n!) to O(2n) establishing an upper bound on the complexity. Recently, a stronger necessary condition of optimality for (P), improving the latter bound by factor O( 1√ n), has been shown in [2]. There are also known some algorithmic results for (P). In [4] have been proposed for (P) two greedy algorithms, based on properties of some functions of deteriora- tion rates called signatures. Another algorithm for the problemhas been proposed in [7]. Finally, in [5] and [9] have been proposed for (P) two fully polynomial- time approximation schemes (FPTASes). 4 Our results Our approach to solving problem (P), in preliminary form presented in [3], can be described as follows. LetC(a) be the vector of job completion times,A(a) be an n×n square matrix with 1′s on the main diagonal, components aj = 1+αj of the sequence a multiplied by −1 below the main diagonal and equal to 0 otherwise, 34 The First International Workshop on Dynamic Scheduling Problems and d = (1, 1, . . . , 1)⊺. Then, an equivalent formulation of problem (P) is as follows: min WP(a) = ∥C(a)∥1 subject to A(a)C(a) = d, where the minimization ofWP(a) is taken over all a ∈ Perm(a0). Since any optimal solution to (P) must be a V-shaped sequence, we consider the polyhedron of all 2n such V-sequences for a given a0. Next, we attach to each ver- tex of this polyhedron a permutation matrix of a special kind and consider the convex hull of such permutation matrices, which coincides with n-dimensional polyhedron of all doubly stochastic matrices of a special kind. This convex polyhe- dron, in turn, we use in a new formulation of problem (P), to which we apply the primal-dual interior point method, [10]. In order to make our variant of interior point method more computationally ef- ficient, we propose to replace in the interior point method the Newton method by an another method, preserving the same size of matrices but without using theHessian inverse. We also propose a further reduction of memory usage by the using of a steepest descent method to the goal function with the barrier and the barrier and penalty components added, respectively. 5 Future research Our method is a new approach to solving problem (P). However, though pre- liminary experiments show that it works quite well in practice, provided a good starting point has been selected, some further refinements such as decreasing the cost of numerical inversion of some matrices or coping with the size of Hessian used in computations are needed. References [1] S. Gawiejnowicz, Time-Dependent Scheduling, Springer, Berlin–Heidelberg, 2008. [2] S. Gawiejnowicz, W. Kurc, A new necessary condition of optimality for a time-dependent scheduling problem, in submission. [3] S. Gawiejnowicz, W. Kurc, Memory-efficient interior point method for solv- ing a time-dependent scheduling problem,The 13th Workshop on Advances in Continuous Optimization, University of Edinburgh, 2015. [4] S. Gawiejnowicz, W. Kurc, L. Pankowska, Analysis of a time-dependent scheduling problem by signatures of deterioration rate sequences. Discrete Applied Mathematics, 154 (2006), 2150–2166. June 30 – July 1, 2016, Poznań, Poland 35 [5] S. Gawiejnowicz, W. Kurc, L. Pankowska, Solving a permutation problem by a fully polynomial time approximation scheme, Discussiones Mathematicae: Differential Inclusions, Control and Optimization, 30 (2010), 191–203. [6] J. Gondzio, Interior point method 25 years later, European Journal of Opera- tional Research, 218 (2012), 587–601. [7] M. Kubale, K. M. Ocetkiewicz, A new optimal algorithm for a time- dependent scheduling problem, Control & Cybernetics, 38 (2009), 713–721. [8] G. Mosheiov, V-shaped policies in scheduling deteriorating jobs,Operations Research, 39 (1991), 979–991. [9] K. M. Ocetkiewicz, A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem, European Journal of Operational Research, 203 (2010), 316–320. [10] M. Ulbrich, S. Ulbrich, L. Vincente, A globally convergent primal-dual interior point filter method for nonlinear programming, Mathematical Pro- gramming, Series A, 100 (2004), 379–410. 36 The First International Workshop on Dynamic Scheduling Problems Minmax scheduling with acceptable lead-times: Extensions to position-dependent processing times, due-window and job rejection Enrique Gerstl The Hebrew University & Jerusalem College of Technology, Jerusalem, Israel Baruch Mor Ariel University, Ariel, Israel Gur Mosheiov* The Hebrew University, Jerusalem, Israel Keywords: scheduling, singlemachine, due-date assignment, position-dependent processing times, minmax, job rejection 1 Introduction The goal in standard scheduling problems is to find the job schedule that min- imizes a certain measure. In scheduling and due-date assignment problems, an additional objective is to find the optimal due-dates (see, e.g., Gordon et al. [3]). Scheduling literature contains three main categories of due-date assignment prob- lems: (1) the setting that all the jobs share a common due-date (denoted by CON), (2) the case when due-dates are assigned to jobs as a (mostly linear) function of their processing times (denoted by SLK), (3) the case when due-dates are de- termined by penalties for exceeding pre-specified deadlines (denoted by DIF). In this talk, we focus our attention on the latter model. 2 Related research The DIF model was introduced by Seidmann et al. [6]. Their model is based on the assumption that there are specific ”lead times that customers consider to be reasonable and expected” [6, p. 394]. As a result, a due-date that exceeds its acceptable lead-time is penalized. Several extensions of the basic DIF model have been published. Shabtay and Steiner [8] considered the case of job-dependent lead- times. Shabtay and Steiner [9, 10] and Leyvand et al. [4] studied the DIF model with controllable job processing times. Wang et al. [11] focused on a model with a learning effect and deteriorating jobs. Finally, Mor et al. [5] studied the minmax version of DIF, which is the setting studied in this talk. * Speaker, e-mail: msomer@huji.ac.il 37 In the above papers, with the exception ofWang et al. [11], one assumes constant, i.e., position-independent job processing times. However, in many applications this classical assumption is not valid. Phenomena like learning, where processing times decrease when jobs are delayed, or aging/deterioration, when processing times increase as a function of the job position or time, are common examples. 3 Our results The main extension of the DIF model proposed in this talk concerns general position-dependent processing times. In particular, unlike most previously published studies, we do not restrict the job processing times to follow any given function, or even to be monotone, i.e., to reflect learning or aging. To the best of our knowledge, there are no published studies combining the DIF model and general position-dependent processing times. We extend the DIF model in two directions. First, we extend the DIF model, with general position-dependent job processing times, to a setting of a Due-Window for acceptable Lead-times that we denote as DWL. The underlying assumption of DWL is that a time interval exists, such that due-dates assigned to bewithin this in- terval are not penalized. The additional lower bound on the acceptable lead-time reflects, e.g., the time needed by the customer for preparation of storage space. A due-date assigned to be prior to this lower bound is not acceptable by the cus- tomer, and a cost for an early due-date is incurred. The most relevant references for this extension are Gerstl and Mosheiov [1, 2], who recently studied the min- max and minsum versions of DWL with position-independent processing times. The second extension of DIF considered here is a setting allowing job rejection. Indeed, as indicated by a number of researchers in the last decade, in many real- life situations the scheduler may decide to process only a subset of jobs. Each unprocessed (”rejected”) job incurs a job-dependent penalty, and the total cost of the rejected jobs becomes a factor in the objective function. We refer the reader to the survey paper on scheduling with job rejection by Shabtay et al. [7]. The extension ofDIF to the setting of general position-dependent processing times is shownhere to be solved in polynomial time by solving a single linear assignment problem. The extension of DIF to the setting of DWL with position-dependent processing times is shown to remain polynomially solvable. Finally, the prob- lem of DIF with job rejection is proved to be NP-hard. An efficient pseudo- polynomial dynamic programming algorithm is introduced, proving that this extension isNP-hard in the ordinary sense. Numerical tests we conducted show that this algorithm is extremely efficient, and instances with hundreds of jobs are solved in a few seconds. 38 The First International Workshop on Dynamic Scheduling Problems References [1] E. Gerstl, G. Mosheiov, Minmax due-date assignment with a time win- dow for acceptable lead-times, Annals of Operational Research, 211 (2013), 167–177. [2] E. Gerstl, G. Mosheiov, Scheduling with a due-window for acceptable lead- times, Journal of the Operational Research Society, 66 (2015), 1578–1588. [3] V. S. Gordon, J-M. Proth, C. Chu, A survey of the state-of-the-art of com- mon due date assignment and scheduling research, European Journal of Operational Research, 139 (2002), 1–25. [4] Y. Leyvand, D. Shabtay, G. Steiner, A unified approach for scheduling with convex resource consumption functions using positional penalties, European Journal of Operational Research, 206 (2010), 301–312. [5] B. Mor, G. Mosheiov, D. Shabtay, A note: Minmax due-date assignment problem with lead-time cost, Computers & Operations Research, 40 (2013), 2161–2164. [6] A. Seidmann, S. S. Panwalkar, M. L. Smith, Optimal assignment of due-dates for a single processor scheduling problem, International Journal of Produc- tion Research, 19 (1981), 393–399. [7] D. Shabtay, N. Gaspar, M. Kaspi, A survey on offline scheduling with rejec- tion, Journal of Scheduling, 16 (2013), 3–28. [8] D. Shabtay, G. Steiner, Two due-date assignment problems in scheduling a single machine, Operations Research Letters, 34 (2006), 683–691. [9] D. Shabtay, G. Steiner, The single-machine earliness-tardiness schedul- ing problem with due-date assignment and resource-dependent processing times, Annals of Operations Research, 159 (2008), 25–40. [10] D. Shabtay, G. Steiner, Optimal due date assignment in multi-machine scheduling environments, Journal of Scheduling, 11 (2008), 217–228. [11] J-B. Wang, L. Liu, C. Wang, Single machine SLK/DIF due window assign- ment problem with learning effect and deteriorating jobs, Applied Mathe- matical Modeling, 37 (2013), 8394–8400. June 30 – July 1, 2016, Poznań, Poland 39 An ”almost-exact” solution to speed scaling scheduling of parallel jobs with preemption Alexander Kononov* Sobolev Institute of Mathematics, Novosibirsk, Russia Yulia Kovalenko Sobolev Institute of Mathematics, Novosibirsk, Russia Keywords: speed scaling, parallel jobs, approximation algorithms 1 Introduction In our talk, we consider two basic variants of scheduling multiprocessor jobs. We are given a set of parallel jobs, each one specified by its release date, deadline and processing volume, and a set of speed-scalable processors. In the first variant, the processing of job j simultaneously requires precisely sizej processors. In the sec- ond variant, the execution of job j simultaneously needs a prespecified subset fixj of dedicated processors. Note that the parallel execution of parts of the same job is not allowed. Moreover, the execution of each job can be interrupted and resumed without incurring any cost or delay. According to definitions given in literature on scheduling theory, we consider rigid jobs and single mode multiprocessor tasks (jobs), respectively [7]. We consider the standard model of speed-scaling, in which if a processor runs at speed s, then the energy consumption is sα units of energy per time unit, where α > 1 is a constant. We assume that if processors execute the same job simultane- ously, then all these processors run at the same speed. Each job has to execute a work volume w and since processors may change their speed, a job may be com- pleted faster (or slower) compared to the timewneeded for its execution at speed 1. The goal is to find a feasible schedule respecting the release dates and deadlines of all jobs such that the total energy consumption is minimized. We will denote the speed scaling problem with rigid jobs by Π1 and the speed scaling problem with single mode multiprocessor jobs by Π2. 2 Related research For the preemptive single-processor case, Yao et al. [9] proposed an optimal al- gorithm for finding a feasible schedule with minimum energy consumption. The * Speaker, email: alvenko@math.nsc.ru 41 case when there are availablem parallel processors and single-processor jobs has been solved optimally in polynomial time, provided that the preemption and the migration of jobs are allowed [1, 3, 5]. We note that the migration of jobs is equiv- alent to the possibility to execute a parallel job in different modes. Albers et al. [2] considered the problem on parallel processors in the case when the preemption of the jobs is allowed but not theirmigration. They proved that it is solvable in polynomial time for instances with agreeable deadlines and unit-work jobs. For general instances with unit-work jobs, they proved that the problem becomes strongly NP-hard and proposed an (αα24α)-approximation algorithm. For the case where the jobs have arbitrary works, the problem was proved to be NP-hard even for instances with common release dates and common deadlines. Albers et al. [1] proposed a 2(2− 1 m) α-approximation algorithm for instances with common release dates, or common deadlines, and an (αα24α)-approximation al- gorithm for instances with agreeable deadlines. Greiner et al. [8] gave a generic reduction transforming an optimal schedule for the problem on parallel proces- sors with migration to a B⌈α⌉-approximate solution for the problem on parallel processors with preemptions but without migration, where B⌈α⌉ is the ⌈α⌉-th Bell number. (The latter result holds only for α ≤ m.) Cohen-Addad et al. [6] showed that the problem without migration is APX -hard, even for jobs with common release date, common deadline and work volumes possess the values 1, 3 or 4. Bampis et al. [4] studied the heterogeneous preemptive problem on parallel pro- cessors where every processor i has a different speed-to-power function, sα(i), and both the life interval and the work of jobs are processor-dependent. For themigra- tory variant, they proposed an algorithm returning a solution within an additive factor of ε far from the optimal solution. The algorithm runs in time polyno- mial to the size of the instance and to 1 ε . For the non-migratory variant, Bampis et al. [4] presented an (1+ ε)αB̃α-approximation algorithm, where B̃α is the α-th generalized Bell number. To the best of our knowledge, no one considered the speed scaling scheduling of parallel jobs. Formore information on scheduling problems with parallel jobs, we refer the reader to the survey book by Drozdowski [7]. 3 Our results We present two algorithms for problems Π1 and Π2.We first formulate the prob- lems as a linear programming (LP) configuration with an exponential number of variables and a polynomial number of constraints. Surprisingly, we use the same LP configuration for both problems. First, we prove that for any ε > 0 there is a feasible solution of the LP with energy consumption at most OPT + ε, where 42 The First International Workshop on Dynamic Scheduling Problems OPT is an optimal solution of the original problem. Then, we consider the dual LP and we show how to use the ellipsoid algorithm to it and obtain an optimal so- lution for the primal LP. For this purpose, we provide two separation oracles, one for the problem Π1 and one for Π2, i.e. we present two algorithms which given a solution for the dual LP decides if this solution is feasible or otherwise it identi- fies a violated constraint. More precisely, we get the following results. Given an instance of Π1 with m processors, we can solve the separation problem for Π1 in time polynomial in m, 1 ε and size of the instance. Thus, we have a polynomial time algorithm if m is fixed, and a pseudo-polynomial time algorithm if m is a part of the input. Given an instance of Π2 with |fixj| = 2 for all jobs, we can solve the separation problem for Π2 in time polynomial in 1 ε and size of the instance. As we can compute an optimal solution for the dual LP, we can also find an opti- mal solution for the primal LP by solving it with the variables corresponding to the constraints that were found to be violated during the run of the ellipsoid algo- rithm and setting all other primal variables to zero. Our two main results can be formulated as follows. Theorem 1. A schedule for the speed scaling problem with rigid jobs of energy con- sumption OPT+ ε can be found in time polynomial in m, 1 ε and size of the instance. Recall that if the number of processors used by a job is chosen by the scheduler, and it can be changed at runtime, then such a job is called amalleable job [7]. Our algorithm can be generalized for the speed scaling problem with malleable jobs. Theorem2. A schedule for the speed scaling problemwith singlemode two-processor jobs of energy consumption OPT+ ε can be found in time polynomial in 1 ε and size of the instance. In our talk, we assume that a continuous spectrum of processor speeds is available. If only a finite set of discrete speed levels is available, then our algorithm finds an optimal solution. The complexity status of both problems with continuous spectrum of speed is open. We also prove ordinaryNP-hardness of Π1, when the number of processors is a part of the input and strongNP-hardness of Π2, when |fixj| = 3 for all jobs. Acknowledgments Supported by the RSF grant No 15-11-10009. June 30 – July 1, 2016, Poznań, Poland 43 References [1] S. Albers, A. Antoniadis, G. Greiner, On multi-processor speed scaling with migration: Extended abstract, The 23rd ACM Symposium on Parallelism in Algorithms and Architectures, ACM, 2011, pp. 279–288. [2] S. Albers, F. Müller, S. Schmelzer, Speed scaling on parallel processors, The 19th ACM Symposium on Parallelism in Algorithms and Architectures, ACM, 2007, pp. 289–298. [3] E. Angel, E. Bampis, F. Kacem, D. Letsios, Speed scaling on parallel processors with migration, Lecture Notes in Computer Science, 7484 (2012), pp. 128–140. [4] E. Bampis, A. Kononov, D. Letsios, G. Lucarelli, M. Sviridenko, Energy effi- cient scheduling and routing via randomized rounding, The 33th IARCS An- nual Conference on Foundations of Software Technology and Theoretical Com- puter Science, Leibniz International Proceedings in Informatics, 24 (2013), pp. 449–460. [5] B. D. Bingham, M. R. Greenstreet, Energy optimal scheduling on multipro- cessors with migration, The IEEE International Symposium on Parallel and Distributed Processing with Applications, IEEE, 2008, pp. 153–161. [6] V. Cohen-Addad, Z. Li, C. Mathieu, I. Milis, Energy-efficient algorithms for non-preemptive speed-scaling, Lecture Notes in Computer Science, 8952 (2015), pp. 107–118. [7] M. Drozdowski, Scheduling for Parallel Processing, Springer-Verlag, London, 2009. [8] G. Greiner, T. Nonner, A. Souza, The bell is ringing in speed-scaled multi- processor scheduling,The 21st ACM Symposium on Parallelism in Algorithms and Architectures, ACM, 2009, pp. 11–18. [9] F. Yao, A. Demers, S. Shenker, A scheduling model for reduced CPU energy, The 36th Annual Symposium on Foundations of Computer Science, IEEE, 1995, pp. 374–382. 44 The First International Workshop on Dynamic Scheduling Problems Workforce planning for cyclic production of multiple parts Mikhail Y. Kovalyov* National Academy of Sciences of Belarus, Minsk, Belarus Xavier Delorme École des Mines de Saint-Étienne, Saint-Étienne, France Alexandre Dolgui École des Mines de Nantes, Nantes, France Keywords: workforce assignment, production line, supply chain 1 Introduction This presentation is motivated by the problems of workforce planning in the pro- duction of vehicle engines on a transfer line, see Battaïa et al. [1]. There is given a paced transfer line withm stations on which vehicle parts of a set P = {1, 2, . . . , k} are manufactured. Each part visits the stations in the same order 1, 2, . . . ,m and fully occupies any station in the time period between its arrival and departure. With a time step C called cycle time, a part on station i de- parts from this station and immediately arrives to station i+1, i = 1, 2, . . . ,m−1, a new part arrives to station 1 and the part at station m leaves the line. Activities taking place between two successive part moves are called (production) cycle. If part j is handled on station i in a cycle, then the duration of all operations on this part at this station in this cycle is a non-increasing function pij(xij) of the number of identical workers xij assigned to station i and part j in this cycle. Workers as- signed to different stations perform their operations in parallel. They do notmove from one station to another in the same cycle, however, they can move instantly to another station after the cycle has been finished. To be feasible with respect to the cycle time, relation pij(xij) ≤ Cmust be satisfied for each station and each part in each cycle. Besides, technological constraints define lower and upper bounds on the values xij in each cycle: aij ≤ xij ≤ bij, i = 1, 2, . . . ,m, j ∈ P. A requirement of the global supply chain is that the production keeps a given proportion of the manufactured parts. To address this issue, the notion of aMin- imal Part Set (MPS) is used. Let the part proportion be given by the numbers w1,w2, . . . ,wk, wherewj is the percent of parts j to bemanufactured, and letGCD denote the greatest common divisor of the numbersw1,w2, . . . ,wk. Let us denote oj = wj GCD , where j ∈ P and n = ∑k j=1 oj. MPS is the multiset that consists of oj copies of each part j, j ∈ P. * Speaker, email: kovalyov_my@newman.bas-net.by 45 An MPS sequence is a part sequence π = (j1, j2, . . . , jn), jr ∈ P, r = 1, 2, . . . , n, in which each part j occurs oj times, j ∈ P. According to the MPS sequence π, the parts visit the line cyclically in the order j1, j2, . . . , jn, j1, j2, . . . , jn, . . . In each cycle, each station is assigned a part and this arrangement can be represented by a sequence σ = (j′1, j′2, . . . , j′m), where j′h ∈ P is the part assigned to station h = 1, 2, . . . ,m. We call such an arrangement a Station-Part matching (SP-matching). There is a 1-1 correspondence between distinct cycles and distinct SP-matchings. GivenMPS sequence π = (j1, j2, . . . , jn), let’s consider a digraph G(π)with the set of nodes {j1, j2, . . . , jn} and the set of arcs {(j1, j2), (j2, j3), . . . , (jn−1, jn), (jn, j1)}. Thus, G(π) is the graph called cycle. We say that an SP-matching σ is π-feasible, if and only if it is a path in the graph G(π), with possible node repetition if m > n. For example, ifm = n+ 1, then σ = (j2, j3, . . . , j1, j2) is π-feasible, and, ifm = 3, then σ = (j6, j7, j8) is π-feasible. Let Φ(π) denote the set of all π-feasible SP- matchings. We have |Φ(π)| = n. Further, let x(σ)i denote the number of workers assigned to station i in the cycle defined by the SP-matching σ, i = 1, 2, . . . ,m. The total number of workers used in this cycle is equal to ∑m i=1 x (σ) i . Denote by x the structure with the entries x(σ)i , i = 1, 2, . . . ,m, σ ∈ Φ(π). The total number of workers used in the long run of the MPS sequence π = (j1, j2, . . . , jn) is equal to T(π, x) = maxσ∈Φ(π){ ∑m i=1 x (σ) i }. The problem is to determine anMPS sequence π and the number of workers assigned to each station in each cycle, determined by the structure x, such that the maximum of the total number of workers over all cycles, T(π, x), is minimized. We denote this problem as MinMaxSum. 2 Related research ProblemMinMaxSumhasmuch in commonwith the problem studied by Lee and Vairaktarakis [2]. However, there are two differences. Firstly, the authors assume that the MPS sequence is not repeated cyclically: the line is free before the first part of anMPS sequence arrives to the first station and the production stops when the last part of this sequence departs from the last station. Secondly, they assume that the workforce requirements are fixed, that is, aij = bij, i = 1, 2, . . . ,m, j ∈ P, in our notation. We denote the problem in [2] as Fix. Lee and Vairaktarakis proved that this problem is solvable in O(n log n) time if m = 2, it is NP-hard in the strong sense if m = 3, and they suggested an integer linear programming formulation, lower bounds and heuristics. ProblemMinMaxSumwith station independent workforce requirements belongs to the class of Minmaxsum Traveling Salesman Problems (TSPs), which includes BottleneckTSP, intersects with TSPunderCategorization, and it is relevant to the k-Neighbor TSP and Maximum Scatter TSP. 46 The First International Workshop on Dynamic Scheduling Problems We show that MinMaxSum is equivalent to the same problem without the cycle time constraints pij(xij) ≤ C and with aij = bij = wij for appropriately defined fixed workforce requirements wij, i = 1, 2, . . . ,m, j ∈ P, propose a brute force algorithm for this problem, prove strongNP-hardness for the case ofm = 3 and for the case ofm = 4 and station independent workforce requirements (wij = wj, i = 1, 2, . . . ,m, j ∈ P), and propose an O(k log k) algorithm for the case m = 2 and station independent workforce requirements. 3 Reduction to fixed workforce requirements Consider an MPS sequence π. Observe that some parts can be missing in an SP- matching σ ∈ Φ(π), but, for any part, there exists an SP-matching σ ∈ Φ(π), in which this part is present on any station. This observation implies two state- ments: 1) the cycle time constraint and the lower and upper bounds on the num- ber of workers are satisfied if and only if, for each pair (i, j), there exists a num- ber of workers x such that pij(x) ≤ C and aij ≤ x ≤ bij, and 2) statement 1) is satisfied, that is, problem MinMaxSum has a solution, if and only if, for each pair (i, j), the optimal number of workers is fixed to be equal to wij := min{x | pij(x) ≤ C, aij ≤ x ≤ bij}, assuming that pij(bij) ≤ C for all i and j. If functions pij(x) are invertible, then wij = max{aij, ⌈p−1 ij (C)⌉}, otherwise, wij can be found in O(log2(bij − aij)) time by a bisection search over the range [aij, bij]. Thus, in O(mk log2maxi,j{bij−aij}) time,MinMaxSum reduces to the same problemwith no cycle time constraints and with the fixed workforce requirements wij, which is to minimize T(π) = max { F(σ) = ∑m i=1 wi,j′i | σ = (j′1, j′2, . . . , j′m) ∈ Φ(π) } . Assume without loss of generality that o1 = mini=1,2,...,k{oi}. Denote by Π the set ofMPS sequences, inwhich part 1 is in the first place. Set n̂ = n−1, ô1 = o1−1 and ôi = oi, i = 2, 3, . . . , k. We have |Π| = Cô1 n̂ · Cô2 n̂−ô1 · · ·C ôk ôk = n̂! ô1!ô2! · · · ôk! = (n− 1)! (o1 − 1)!o2!o3! · · · ok! . MinMaxSum reduces to minimizing T(π) for π ∈ Π. Since |Φ(π)| = n, each value T(π) can be calculated in O(mn) time. Hence, MinMaxSum can be solved in O(mn|Π|) = O ( n!m (o1−1)!o2!o3!···ok! ) time. 4 Complexity results Theorem 1. MinMaxSum isNP-hard in the strong sense for the case m = 3 and for the case m = 4 and wij = wj for i = 1, 2, . . . ,m and j ∈ P. June 30 – July 1, 2016, Poznań, Poland 47 Weuse reductions fromNumerical 3-DimensionalMatching and 3-Partition for the first and the second mentioned case, respectively. Letm = 2 andworkforce requirements bewij = wj for i = 1, 2 and j = 1, 2, . . . , k. Assume that part copies are numbered 1, 2, . . . , n and each part copy r is associ- ated with workforce requirement w0 r which is equal to the workforce requirement of its part: w0 r = wj if r is a copy of part j. Number part copies in the Least Work- force Requirement (LWR) order such that w1 ≤ w2 ≤ · · · ≤ wn. We call sequence of part copies π = (1, n, 2, n − 1, 3, n − 2, 4, . . .), which includes all n copies, Up-and-Down sequence. Theorem2. TheUp-and-Down sequence is optimal forMinMaxSum if m = 2 and wij = wj for i = 1, 2 and j ∈ P. The Up-and-Down sequence can be represented using O(k) memory units be- cause copies of the same part appear consecutively in the LWR order. This concise representation of the Up-and-Down sequence can be constructed in O(k log k) time by sorting parts in the non-decreasing order of their workforce requirements and employing this order in the description of theUp-and-Down sequence of part copies. Thus, MinMaxSum with m = 2 and wij = wj for i = 1, 2 and j ∈ P can be solved in O(k log k) time. 5 Future research In the future, it is interesting to establish computational complexity of the open cases of MinMaxSum with fixed parameters m and/or k, and general or station independent workforce requirements. ILP formulations and (meta)heuristics for the general case are of a practical interest. References [1] O. Battaïa, X. Delorme, A. Dolgui, J. Hagemann, A. Horlemann, S. Kovalev, S. Malyutin, Workforce minimization for a mixed-model assembly line in the automotive industry, International Journal of Production Economics, 170 (2015), 489–500. [2] C-Y. Lee, G. L. Vairaktarakis, Workforce planning in mixed model assembly systems, Operations Research, 45 (1997), 553–567. 48 The First International Workshop on Dynamic Scheduling Problems Directed sets, Möbius inversing formula and time-dependent scheduling on precedence-constrained machines Wiesław Kurc* AdamMickiewicz University in Poznań, Poznań, Poland Stanisław Gawiejnowicz AdamMickiewicz University in Poznań, Poznań, Poland Keywords: directed sets, Möbius inversing formula, time-dependent scheduling, total weighted completion time, maximum completion time 1 Introduction The aim of this talk is to present some preliminary results on scheduling jobs with variable processing times onmachines endowed by a partial order. In other words, we consider scheduling problems in which the directed chain of machines typi- cal for such machine systems as flow shop is replaced by a more general directed set. We illustrate the idea by an example in which available machines compose a directed tree. Applying a matrix approach [1], equivalent toMöbius inversing for- mula over incidence algebra [2], we formulate two results concerning scheduling linearly deteriorating jobs on suchmachine systemswith the objective tominimize the total weighted completion time or the maximum completion time. 2 Problem formulation We consider the following problem. The set J of n+ 2 jobs has to be processed on the setM ofm+2machines. Jobs are divided into real jobs and artificial jobs. The processing time of real job Ji ∈ J varies according to the function pi(t) = bi + αit, where t denotes the starting time of the job, bi ≥ 0 and αi ≥ −1 for 1 ≤ i ≤ n. The processing time of artificial job J0 is fixed, p0(t) = b0. Artificial job Jn+1 has no processing time and its meaning is to simplify the problem formulation. To each job Ji ∈ J, excluding artificial job J0, there is defined weight ωi+1, indicating the significance of the completion timeCi of job Ji from the perspective of job Ji+1. Jobs J1, J2, . . . , Jn are processed on real machines M1,M2, . . . ,Mn, while artificial jobs J0 and Jn+1 are processed on artificial machines M0 and Mn+1, respectively. On machines M0,M1, . . . ,Mn+1 there is defined a partial order and all of them are available for processing from time C0 ≥ 0. * Speaker, email: wkurc@amu.edu.pl 49 Since jobs J1, J2, . . . , Jn are fully characterized by n triplets σi = (bi, ai,ωi), fol- lowing [1] we use the table σ = (σ0, σ1, . . . , σn+1) =  b0 b1 b2 bn − − a1 a2 an − − ω1 ω2 ωn ωn+1  in which triplets σ0 = (b0,−,−) and σn+1 = (−,−,ωn+1) correspond to artifi- cial jobs J0 and Jn+1, respectively. (Since any such a table corresponds to a non- delay schedule, we will denote the table and the schedule by the same symbol.) Given C0 and σ, job completion times are equal to C1(σ) = C0 + p1(C0) = b1 + a1C0 and Ci(σ) = bi + aiCi−1(σ), where Ci(σ) denotes the completion time of job Ji in schedule σ, C0(σ) ≡ C0, ai = 1 + αi and 1 ≤ i ≤ n. The aim is to find a schedule σ minimizing the total weighted completion time, ∑n i=0 ωi+1Ci(σ), or the maximum completion time, max{Ci(σ) : 1 ≤ i ≤ n}. The above problem can be concisely formulated in a matrix form. Let σ◦ and Perm(σ◦) denote the table corresponding to the initial order of jobs given in in- put instance and the set of all permutations of the triplets σ1, σ2, . . . , σn in σ◦, respectively. Then, the problem under consideration is equivalent to minω⊺C(σ) = ∑n i=0 ωi+1Ci subject to A(σ)C(σ) = b, where σ ∈ Perm(σ◦), [1]. In order to illustrate our ideas, let us consider the following example. Denote by M = {Mi,Ms,Mj,Mk,Ml,Mm} the set of machines endowed with the partial orderMi ⪯ Mk ⪯ Ml ⪯ Mm,Mj ⪯ Mk, andMs ⪯ Ml. In other words,M forms a directed tree with the root atMm and three leavesMi,Mj andMs.The table σ◦ of triplets describing jobs is in the form of σ◦ =  bi bs bj bk bl bm − − − − ak al am − − − − ωk ωl ωm ωn  . Then Ci(σ◦) = bi,Cs(σ◦) = bs,Cj(σ◦) = bj andCk(σ◦) = Ci(σ◦)+pk(Ci(σ◦))+ Cj(σ◦) + pk(Cj(σ◦)) = akCi(σ◦) + bk + akCj(σ◦) + bk, Cl(σ◦) = Ck(σ◦) + 50 The First International Workshop on Dynamic Scheduling Problems pl(Ck(σ◦)) + Cs(σ◦) + pl(Cs(σ◦)) = alCk(σ◦) + bl + alCs(σ◦) + bl and, finally, Cm(σ◦) = amCl(σ◦) + bm. Matrix equation A(σ◦)C(σ◦) = b is in the form of 1 1 1 −ak −ak 1 −al −al 1 −am 1   Ci Cs Cj Ck Cl Cm  =  bi bs bj 2bk 2bl bm  . Hence, C(σ◦) = A−1(σ◦)b with lower triangular matrix A−1(σ◦). Therefore, ω⊺C(σ◦) = biωi + bjωj + ( ak ( bi + bj ) + 2bk ) ωk+ + ( akal ( bi + bj ) + 2bl + al (2bk + bs) ) ωl+ + ( akalam ( bi + bj ) + 2ambl + bm + alam (2bk + bs) ) ωm + bsωs, since C(σ◦) =  bi bs bj akbi + akbj + 2bk akalbi + akalbj + 2albk + 2bl + albs akalambi + akalambj + 2alambk + 2ambl + bm + alambs  . Job completion times can be computed in a few different ways. If we assume, as above, that in a schedule σ the processing at node k applies the same function pk(t) to job completion times Ci(σ), Cj(σ) from the previous stage, then Ck(σ) = (Ci(σ) + pk(Ci(σ))) △ (Cj(σ) + pk(Cj(σ))), where △≡ +. Alternatively, one can assume that△≡ max. Finally, we can assume thatCk(σ) = (Ci(σ)+pi(Ci(σ))) △ (Cj(σ) + pj(Cj(σ))) = aiCi(σ) + ajCj(σ) + bi + bj, where △≡ +. In the latter case, the objective function becomes ω⊺C(σ) = ωkCi(σ) + ωlCs(σ) + ωkCj(σ) + ωlCk(σ) + ωmCl(σ) + ωnCm(σ). 3 Our results Ourmain results are based on twoobservations. First, notice thatC(σ) = A−1(σ)b is a form ofMöbius inversing formula ([2]) over incidence algebraA(M) of all real- valued functions f over M × M such that f(Mi,Mj) = 0 unless Mi ⪯ Mj, where ⪯ is a partial order in M. Second, notice that the incidence algebras give us the June 30 – July 1, 2016, Poznań, Poland 51 mathematical background for time-dependent scheduling onmachines related by the partial order ⪯. For instance, from [2] it follows that A−1(σ) exists and is a triangular matrix for any partial order onM. Keeping in mind the observations, our two main results can be stated as follows. Theorem 1. Let M be the set of n machines endowed with partial order ⪯ such that M is a directed set. Let J be the set of n jobs described by the table σ with ωi = bi = 1 for 0 ≤ i ≤ n + 1, respectively. Moreover, let σ∗ ∈ Perm(σ◦) be an optimal schedule for problem (P) with the ∑ ωj+1Cj criterion. Then elements ai of σ∗ considered along any chain connecting beginning and final elements in M must be V-shaped. Theorem 2. Let assumptions of Theorem 1 be satisfied and let σ∗ ∈ Perm(σ◦) be an optimal schedule for problem (P)with the Cmax criterion. Then the elements ai of σ∗ considered along any chain connecting beginning and final elements in M must be non-decreasing. 4 Future research In future research we want to extend our ideas to the case of other forms of job processing times and machine precedence constraints. References [1] S. Gawiejnowicz, W. Kurc, L. Pankowska, Equivalent time-dependent scheduling problems, European Journal of Operational Research, 196 (2009), 919–929. [2] J. P. S. Kung, G-C. Rota, C. H. Yan, Combinatorics: The RotaWay, Cambridge University Press, 2009. 52 The First International Workshop on Dynamic Scheduling Problems Relocation scheduling with optional recycling operations Bertrand M-T. Lin* National Chiao Tung University, Hsinchu, Taiwan Keywords: relocation problem, resource-constrained scheduling, optional recy- cling operations, dynamic programming, maximum completion time 1 Introduction In this talk, we introduce a scheduling problem with a new variant of resource constraints. The new resource constraints are generalizations of renewable and non-renewable resources in the sense that a task when completed will release the resource it has acquired for processing, allowing the amount of released resource to be smaller than, equal to or even larger than the amount of the previously ac- quired resource. Moreover, in order to release the resource back to the common pool, a recycling operationmust be performed. When the amount of the resource is sufficient, some of the recycling operations can be bypassed. The problem is to find a feasible schedule that attains the minimummakespan. 2 Problem formulation The problem under consideration is formally defined as follows. A set of n jobs N = {1, 2, . . . , n} is to be processed on a single machine. Each job j ∈ N is characterized by four non-negative integral parameters: (1) resource requirement aj that is an amount of the resource required to commence the processing of job j, (2) processing time pj that is the processing time of the regular operation of job j, (3) resource yield bj that is an amount of the resource that may be returned by job j when it is completed, (4) resource recycling time qj that is the time required for recycling the bj units of the resource. A common pool of v0 units of a single-type resource is given for processing the jobs ofN. Job j requires and consumes aj units of the resource from the resource pool to commence its processing. Upon its completion, we either perform its recycling operation, taking qj units of time, or directly proceed to the processing of other jobs. If the recycling operation is carried out, then bj units of the resource will be produced and deposited into the common pool. The decision consists of two parts: (1) selecting a subset of re- cycling operations to be performed, and (2) determining a sequence of all regular operations and the selected recycling operations. The derived sequence should * Speaker, email: bmtlin@mail.nctu.edu.tw 53 be feasible subject to the resource constraints in the sense that in the course of execution no job is blocked by insufficiency of the resource. The objective is to minimize the makespan, i.e. the largest completion time of the regular processing operations. We will denote the problem as 1|aj, bj, recl|Cmax. 3 Related research The studied problem is a generalization of the relocation problem formulated as a redevelopment project in the east Boston by Kaplan [2]. Taking into account the temporal issues along the planning horizon, Kaplan [2] addressed the recon- struction time lines of the buildings, which allowed to process multiple buildings in parallel if the available resource permitted this. Kononov and Lin [4, 5] in- vestigated two other objective functions. The first attempt to introduce recycling operations was done by Lin and Huang [6]. In this case, a second working crew is available for performing the recycling operations and the two working crews con- stitute a two-machine flow shop: the first machine is responsible for demolishing the buildings, the second one is used for erecting new buildings. Cheng et al. [1] considered a relocation problem with separate recyclic operations. 4 Our results We start with the following theorem that links the relocation problem and two- machine flow shop scheduling F2||Cmax. Theorem 1. (Kaplan and Amir [3]) Let aj and bj be the machine-one and machine- two processing times of job j in the F2||Cmax problem. Then, the minimum initial resource level guaranteeing the feasibility of a sequence in the relocation problem is equivalent to the total idle time on machine two of the corresponding job sequence in the F2||Cmax problem. Lemma 2. Consider the base relocation problem with only negative jobs, i.e., such that δj = aj − bj < 0 for all j ∈ N. If the initial resource level v0 is sufficient for guaranteeing the existence of feasible schedules of the jobs in N, then v0 is also sufficient for any proper subset of N. Returning to the studied problem, we have the following auxiliary result. Lemma 3. There is an optimal schedule of 1|aj, bj, recl|Cmax in which (1) the com- plete jobs precede the partial jobs, (2) the complete jobs are sequenced by Johnson’s rule, and (3) the partial jobs can be arranged in arbitrary order. To formulate the studied problem, we define binary variable xj = 1 if the recycling operation of job j is performed, and xj = 0 otherwise. 54 The First International Workshop on Dynamic Scheduling Problems Then, the formulation of the problem as an integer program is as follows: Minimize n∑ j=1 xjqj (1) subject to v0 + j−1∑ i=1 xiδi ≥ xjaj, 1 ≤ j ≤ n, (2) v0 + n∑ i=1 xiδi ≥ n∑ i=1 ai(1− xi), 1 ≤ j ≤ n, (3) xj ∈ {0, 1}, 1 ≤ j ≤ n. (4) The left hand side of constraints (4) and (5) gives the resource levels at the com- pletion of jobs in certain positions. Constraints (2) ensure the feasibility of each complete job, and constraints (3) confine the feasibility of the partial jobs. The problem is NP-hard, since it is a generalization of the Knapsack problem. However, it still allows the development of pseudo-polynomial algorithm by dy- namic programing (DP). The design of our DP algorithm differs from most of other ones, in which feasible schedules are constructed by recursion from feasible partial schedules. Namely, infeasibility in our design is allowed during the con- struction course of partial schedules. State f(j, τ, η) is defined for the first j jobs, 1, 2, . . . , j, subject to the conditions that the resource level at the completion of all complete jobs is exactly τ and that the total resource requirement of the partial jobs is exactly η. Many (partial) schedules may correspond to state f(j, τ, η). De- fine f(j, τ, η) as the maximum total length of rejected recycling operations among the schedules corresponding to state (j, τ, η). Dynamic Programming Algorithm for problem 1|aj, bj, recl|Cmax Initialization: For j = 0 to n, τ = 0 to v0 + ∑ i∈N+ δi, η = 0 to ∑ i∈N ai f(j, τ, η) = { 0, if j = τ = η = 0; −∞, otherwise. Recursion: For j = 0 to n, τ = 0 to v0 + ∑ i∈N+ δi, η = 0 to ∑ i∈N ai f(j, τ, η) = { max { f(j− 1, τ − δj, η), f(j− 1, τ, η − aj) + qj } , if τ − δj ≥ aj; f(j− 1, τ, η − aj) + qj, otherwise. Goal: Find max { f(n, τ, η) : 0 ≤ τ ≤ v0 + ∑ j∈N+ δj, 0 ≤ η ≤ τ } . In recursion, condition τ − δj ≥ aj examines whether or not job j is eligible to be scheduled as the last complete job. If job j is eligible, we can schedule it either June 30 – July 1, 2016, Poznań, Poland 55 complete or partial. The inequality η ≤ τ in the goal function is to ensure the fea- sibility of the partial jobs in the schedules corresponding to the states defined by n. The overall computing time is O ( n(v0 + ∑ j∈N+ δj) ∑ j∈N aj ) , which is pseudo- polynomial in terms of the input length, confirming that the 1|aj, bj, recl|Cmax problem cannot be stronglyNP-hard. References [1] T-C. E. Cheng, B. M-T. Lin, H-L. Huang, Makespan minimization in the relocation problem with separate resource recycling operations, Comput- ers & Operations Research, 412 (2011), 4536–4544. [2] E. H. Kaplan, Relocationmodels for public housing redevelopment programs, Planning & Design, 13 (1986), 5–19. [3] E. H. Kaplan, A. Amir, A fast feasibility test for relocation problems, European Journal Operational Research, 35 (1988), 201–205. [4] A. V. Kononov, B. M-T. Lin, On the relocation problems with multiple iden- tical working crews, Discrete Optimization, 3 (2006), 368–381. [5] A. V. Kononov, B.M-T. Lin,The relocation problem tominimize the weighted completion time, Journal of Scheduling, 13 (2010), 123–129. [6] B. M-T. Lin, H-L. Huang, On the relocation problem with a second work- ing crew for resource recycling, International Journal of Systems Science, 37 (2006), 27–34. 56 The First International Workshop on Dynamic Scheduling Problems Financial scheduling with time-dependent resource consumption Krzysztof M. Ocetkiewicz* Gdańsk University of Technology, Gdańsk, Poland Michał Małafiejski Gdańsk University of Technology, Gdańsk, Poland Keywords: financial scheduling, non-renewable resources, time-dependent sche- duling, dynamic programming, approximation schemes 1 Introduction Consider the following scenario. After a period of careless spending, a person finds oneself with a number of loans to repay. Each loan has a known characteris- tic expressed by due date or interest rate. Fortunately, the person is employed, so there are a number of known money gains. Now, arises the question: it is possible to repay all the loans? If it is, how to repay them with the least amount of money? In this talk, we investigate the following problem. We are given a single processor and a number of jobs with zero processing times. The execution of each job re- quires a certain amount of additional, non-renewable resource. This requirement is time-dependent, i.e., for every job a function of time describes the resource re- quirement to process the job at the given moment. The resource is obtained in a number of gains. Each gain is described by the moment the gain occurs and the amount of resource gained. There is no limited capacity for storing the resource and it does not deteriorate with time. All information is known in advance. We start processing at time t0 = 0 and with no resource. This problem models the mentioned above situation in the following way. We (the processor) are facing a number of debts to repay (the jobs). Usually, the num- ber of bank transfers that we can issue at any time is not a limiting factor, so com- pleting such jobs requires virtually no time. On the other hand, enough cash, i.e. resource, is needed to make payments. Finally, the income, i.e. resource gains, increases cash reserves at specified moments. * Speaker, e-mail: Krzysztof.Ocetkiewicz@eti.pg.gda.pl 57 2 Problem formulation There is given one processor and n jobs J = {J1, J2, . . . , Jn} with zero process- ing times. The completion of each job requires consuming a given amount of an additional resource, described by function gi(si) = { ai, if si ≤ di, ai + bi, otherwise, where si is a job’s starting time and ai ∈ Z+, bi ∈ Z+ for i = 1, 2, . . . , n. Each job is completed immediately after being started, i.e., si = Ci for every job. The amount of available resource is 0 at the schedule’s start and increases in moments ti by Gi ∈ Z+ for i = 1, 2, . . . k and t1 < t2 < . . . < tk. The goal is to check whether there exists a feasible schedule such that all jobs are completed. Denote the problem by 1|NR,ZET, gi ∈ {ai, ai + bi} |−. This prob- lem answers the question whether one is able to repay all loans, when missing a due date results in a one-time penalty. We will also extend the above prob- lem to 1|NR,ZET, gi ∈ {ai, ai + bi} | ∑ gj, where the ∑ gj denotes the criterion of minimizing the total amount of resource spent to complete all jobs. This, in turn, can be understood as the minimization of the total cost of repaying all loans. Finally, we substitute the step debt growth rate with linear one, obtaining resource requirement function in the form of gi(si) = ai + bisi. Again, the goal is to answer whether there exists a feasible schedule such that all jobs are completed. We denote the problem by 1|NR,ZET, gi = ai + bisi|−. This model relates to the case when interest rates are enlarging the debt every month. 3 Related research The problems with non-renewable resources are sometimes referred to as financial scheduling, since the resources often represent the amounts of available money, fuel or other valuable (and thus limited) commodities. Such problems received some attention in the last years fromboth theoretical (see [1, 2] for numerous com- plexity results) and practical point of view (pseudo-polynomial algorithms and approximation schemes [4, 5]). Time dependent resources in different context were considered in [3], where resources are renewable but the available amounts change with time. In other models, available non-renewable resource is used to decrease processing time of time-dependent jobs, [6]. 58 The First International Workshop on Dynamic Scheduling Problems 4 Our results Theorem 1. The problem 1|NR,ZET, gi ∈ {ai, ai + bi} |− isNP-complete. Proof. We proceed by a reduction from the Subset Sum problem, in short SS: there is given a sequence Z = {z1, z2, . . . , zn}, where zi ∈ Z+ for 1 ≤ i ≤ n and a number S; is there a subset Z′ ⊂ Z such that ∑ zj∈Z′ zj = S? For a given instance I of SS, we build an instance I′ of 1|NR,ZET, gi ∈ {ai, ai + bi} |− as follows: ai = bi = zi, di = 2 for every item zi in the SS problem, k = 2, t1 = 1, G1 = S, t2 = 3, G2 = 2( ∑n i=1 zi − S). If there exists a positive answer to I, then one can schedule jobs corresponding to elements in the Z′ set at the moment 1 and the remaining jobs at the moment 3. On the other hand, I′ has a positive answer only if jobs scheduled up to the moment 2 will consume exactly S units of the resource, which means that there exists also a positive answer to I. For solving this problem, we will employ a dynamic programming algorithm. Without loss of generality, we can reorder all jobs such that d1 ≤ d2 ≤ . . . ≤ dn. If two jobs have the same due date, we put them in arbitrary order. Let D[i, P] be equal to the smallest amount of resource that must be spent to complete in time jobs from the set Zi = {J1, J2, . . . , Ji} up to the moment di, while gathering total penalty equal to P = ∑ j∈ZPi bj, where ZPi is a subset of Zi containing the penal- ized jobs. If a given value of P cannot be obtained, we set D[i, P] = +∞. Clearly, D[0, 0] = 0, D[i, 0] = ∑ j=1,2,...,i aj and D[0, p] = +∞ for p > 0. We will call the algorithm as Algorithm PP. Lemma 2. Let Si be the total amount of resources available at the moment di, i.e. Si = ∑ j:tj≤di Gj. Then D[i+ 1, P] = min  ai+1 + D[i, P], if ai+1 ≤ Si+1, D[i, P− bi+1], if P ≥ bi+1, +∞ otherwise. (1) In view of Lemma 2, all we need to do is to find the smallest p ∈ {0, 1, . . . , P} such that D[n, p] < +∞ and ∑n i=1 ai + p ≤ Sn, where P = ∑n i=1 bi is the largest value of attainable penalty. Lemma 3. Let b > 0, ε > 0. Transform the instance I of our problem, obtaining instance I′, in such a way that: R = εb n , n ′ = n, k′ = k, a′i = ai, g′j = gj, d′i = di, G′ j = Gj, b′i = ⌈ bi R ⌉ for i = 1, 2, . . . , n, j = 1, . . . , k. Let OPT be the value of the optimal solution to I. Applying Algorithm PP with I′ and P ≥ OPT, we can either find (1 + ε)-approximate solution to instance I or ensure that OPT < b. June 30 – July 1, 2016, Poznań, Poland 59 On the basis of Lemma 3, one can construct a fully-polynomial approximation scheme (an FPTAS) for the problem, which iteratively invokesAlgorithmPP. Each invocationwill either produce the required result orwill decrease the upper bound for optimal solution value. Theorem 4. The problem 1|NR,ZET, gi = ai + bisi|− is stronglyNP-complete. Proof (Sketch). We proceed by a reduction from the 3-Partition problem. For a given instance I of 3-Partition, we build an instance I′ of 1|NR,ZET, gi = ai + bisi|− as follows: n = 3m, k = m, ti = i−1,Gi = iS, gj(t) = zj+zjt for 1 ≤ i ≤ m, 1 ≤ j ≤ 3m. If there exists a positive answer to I, then one can schedule jobs corresponding to elements in the Zi set at the moments i− 1 obtaining a feasible schedule. On the other hand, there exists a valid schedule only if at everymoment ti for 1 ≤ i ≤ m jobs consuming exactly iS units of resource are scheduled, i.e., there exists a set of three jobs, Ja, Jb and Jc, such that i(za + zb + zc) = iS. □ 5 Future research An interesting question arises what happens to the problem when common (unit) or arbitrary processing times of jobs are allowed. References [1] E. R. Gafarov, A. A. Lazarev, F. Werner, Single machine scheduling problems with financial resource constraints: Some complexity results and properties, Mathematical Social Sciences, 62 (2011), 7–13. [2] E. R. Gafarov, A. A. Lazarev, F. Werner, A note on the paper ”Single machine scheduling problems with financial resource constraints: Some complexity results and properties” by E.R. Gafarov et al., Mathematical Social Sciences, 65 (2013), 232. [3] T. Tautenhahn, G. J. Woeginger, Unit-time scheduling problems with time dependent resources, Computing, 58 (1997), 97–111. [4] P. Győrgyi, T. Kis, Aproximation schemes for single machine scheduling with non-renewable resource constraints, Journal of Scheduling, 17 (2014), 135–144. [5] P. Győrgyi, T. Kis, Approximability of scheduling problemswith resource con- suming jobs, Annals of Operations Research, 235 (2015), 319–336. [6] C-M. Wei, J-B. Wang, P. Ji, Single-machine scheduling with time-and- resource-dependent processing times, Applied Mathematical Modelling, 36 (2012), 792–798. 60 The First International Workshop on Dynamic Scheduling Problems Scheduling on identical parallel machines with controllable processing times to minimize the makespan Daniel Oron The University of Sydney Business School, Sydney, Australia Dvir Shabtay* Ben-Gurion University of the Negev, Beer Sheva, Israel George Steiner McMaster University, Hamilton, Ontario, Canada Keywords: scheduling, parallel machines, controllable processing times, total weighted resource consumption, maximum completion time 1 Introduction Scheduling with controllable processing times has been the focus of extensive research for the last three decades, see Shabtay and Steiner [5] for a survey. In contrast to the common assumption in deterministic scheduling saying that job processing times are constant values, in scheduling with controllable process- ing times the job durations are controllable through the allocation of resources to job operations. In this talk, we consider a problem of this type. 2 Problem formulation We focus on the following scheduling problemwith controllable processing times. A set of n jobs J = {J1, J2, ..., Jn} has to processed on a set ofm identical machines M = {M1,M2, ...,Mm} working in parallel. Job preemption is not allowed. The job processing time, pj(uj), is a convex function of the amount of a non-renewable resource, uj, that is allocated to the processing operation, i.e., pj(uj) = ( wj uj ) k, where wj is a positive parameter representing the workload of job Jj and k is a positive constant. A solution S for our scheduling problem is defined by a par- tition τ of set J into m subsets JM1 , JM2 , ..., JMm , where JMi is the set of jobs to be processed on machine Mi, i = 1, 2, . . . ,m, and by a resource allocation vec- tor u = (u1, u2, . . . , un). The quality of a solution is measured by two criteria: the first is the makespan criterion given by Cmax = max i=1,2,...,m ∑ Jj∈JMi pj(uj)  = max i=1,2,...,m ∑ Jj∈JMi ( wj uj )k  (1) 61 and the second criterion is the total weighted resource consumption given by Uv = n∑ j=1 vjuj, (2) where vj is the cost of one unit of resource allocated to the processing operation of job Jj for j = 1, 2, . . . , n. We focus on the following four different problem variations, whereU andK are given parameters: (P1) finding a solution S = (τ, u) minimizingCmax+Uv, (P2) finding a solution S = (τ, u)minimizingCmax subject toUv ≤ U, (P3) finding a solution S = (τ,u)minimizingUv subject to Cmax ≤ K, (P4) identifying a Pareto-optimal solution for each Pareto-optimal point, where a solution SwithCmax(S) = K andUv(S) = U is called Pareto-optimal if there does not exist another solution S′ such that Cmax(S′) ≤ K andUv(S′) ≤ U, with at least one of these inequalities being strict. 3 Related research Shabtay and Kaspi [6] studied the special of the (P2) problem variation, where vj = 1 for j = 1, 2, . . . , n and (i) provided amethod to obtain the optimal resource allocation for problem (P2) as a function of τ, (ii) use the result in (i) to reduce this special case of (P2) to a purely combinatorial problem, and (iii) show that the reduced combinatorial problem is NP-hard when m = 2 by reducing the Partition problem to it. However, the analysis in [6] has some drawbacks. The first is that the analysis is restricted to problem (P2) with vj = 1 for j = 1, 2, . . . , n. The second is that it includes complexity results only for the case where m = 2. Finally, it does not provide any practical tool to solve the problem. Our aim in this talk is to bridge these gaps through the analysis of problems (P1)–(P4). 4 Our results The following lemma presents the optimal resource allocation strategy for (P2) as a function of partition τ. Lemma 1. The optimal resource allocation strategy for (P2) as a function of τ is to assign to any job Jj ∈ JMi r∗j = vju∗j = (θj) k k+1 ∑ Jl∈JMi (θl) k k+1  1 k U w′ G units of resource, where w′ G = m∑ i=1 ∑ Jj∈JMi ( θj ) k k+1  k+1 k = m∑ i=1 ∑ Jj∈JMi aj k′ , k′ = k+1 k > 1, θj = vjwj and aj = ( θj ) k k+1 for j = 1, 2, . . . , n. 62 The First International Workshop on Dynamic Scheduling Problems Based on Lemma 1, we show that the minimal makespan value, considered as a function of τ, can be computed by Cmax(τ, u∗(τ)) = ( w′ G U )k . Since both U and k are constant parameters, problem (P2) reduces to the followingWeighted Workload Partition (WWP) problem: given a set A = {a1, a2, . . . , an} and a parameter k, find a partition τ of set A intom subsets JM1 , JM2 , . . . , JMm such that f(τ) = w′ G = m∑ i=1 ∑ Jj∈JMi aj k′ (3) is minimized. We also show that remaining variations of our problem, i.e., (P1), (P2) and(P4), reduce to theWWP problem as well, and prove the following complexity result by a reduction from the 3-Partition problem. Theorem 2. The decision version of the WWP problem is stronglyNP-complete. We briefly explain how we can provide a fully-polynomial approximation scheme (an FPTAS) for solving the WWP problem with a fixed number of machines, re- gardless of the fact that we could not provide a pseudo-polynomial time algorithm for this problem, as the states of the corresponding dynamic programming (DP) algorithm have to include non-integer values, even if the input of the entire in- stance is restricted to integer values. The fact that an FPTAS can be constructed follows from the fact that a DP algorithm can be constructed for the scaled and rounded version of the problem. By using the appropriate scaling parameter, we can actually ensure that the algorithm runs in polynomial time. Following the method presented in Ibarra and Kim [2], we scale the aj parameters by a con- stant K and then round down the resulting scaled parameters. Let aj = ⌊ aj K ⌋ be the scaled and rounded aj value for j = 1, 2, . . . , n, and let WWP(S& R) be the scaled and rounded version of the WWP problem. Accordingly, our ob- jective in WWP(S& R) is to find a partition τ of set A = {1, 2, . . . , n} into m subsets τ1, τ2, . . . , τm such that f(τ) = ∑m i=1( ∑ j∈τiaj) k′ is minimized. In or- der to present an FPTAS for the WWP problem, we provide a state space gener- ation algorithm that optimally solve the WWP(S& R) in O ( nmQm) time, where Q = ∑n j=1 aj.Then, we prove the following theorem. Theorem 3. Solving the WWP(S&R) problem with K = log(1+ε)Σn j=1aj k′mn and ε ≤ 2 3 yields an FPTAS for the WWP problem. The longest processing time (LPT) heuristic is commonly used for solving the stronglyNP-hard P ||Cmax problem. The heuristic begins by renumbering the n jobs in a non-increasing order of processing times such that p1 ≥ p2 ≥ · · · ≥ pn. Then, for j = 1, 2, . . . , n, the algorithm assigns job Jj to the least loaded machine so far. Graham [1] proved that the LPTheuristic provides ( 43− 1 3m)-approximation June 30 – July 1, 2016, Poznań, Poland 63 algorithm for the P ||Cmax problem. A straightforward modification of the LPT heuristic to solve the WWP problem would be to apply it with the aj parameters replacing the pj parameters. We prove the following theorem. Theorem 4. The modified LPT heuristic is h(m − v, k′, r∗)-approximation algo- rithm for the WWP, where h(m − v, k′, r∗) = (m−v−r∗)(m−v+r∗+1)k′+r∗(r∗+1)k ′ (m−v)(m−v+1)k′ , with D(v) = n∑ j=v+1 aj, v = sup{J1, J2, . . . , Jn : aj ≥ D(j) m−j+1}, A(v) = n∑ j=v+1 aj m−v , and r∗ is the r value that maximizes g(r) = ( A(v) m− v+ 1 )k′ ( (m− v− r)(m− v+ r+ 1)k′ + r(r+ 1)k′ ) . References [1] R. L. Graham, Bounds for certainmultiprocessor anomalies, Bell System Tech- nology Journal, 45 (1966), 1563–1581. [2] O. H. Ibarra, C. E. Kim, Fast approximation algorithms for the knapsack and the sum of subset problems, Journal of the ACM, 22 (1975), 463–468. [3] D. Shabtay, Single and a two-resource allocation algorithms for minimiz- ing the maximal lateness in a single machine scheduling problem, Comput- ers & Operations Research, 31 (2004), 1303–1315. [4] D. Shabtay, M. Kaspi, Minimizing the total weighted flow time in a single ma- chine with controllable processing times, Computers & Operations Research, 31 (2004), 2279–2289. [5] D. Shabtay, G. Steiner, A survey of scheduling with controllable processing times, Discrete Applied Mathematics, 155 (2006), 1643–1666. [6] D. Shabtay, M. Kaspi, Parallel machine scheduling with a convex resource consumption function, European Journal of Operations Research, 173 (2006), 92–107. 64 The First International Workshop on Dynamic Scheduling Problems Precedence constrained position-dependent scheduling on parallel machines via schedule transformations Bartłomiej Przybylski* AdamMickiewicz University in Poznań, Poznań, Poland Keywords: scheduling, position-dependent jobs, precedence constraints, poly- nomial algorithms, maximum completion time, total weighted completion time 1 Introduction In many scheduling problems one cannot assume that job processing times are fixed. There are two main groups of scheduling problems with variable job pro- cessing timeswhich are considered in literature: time-dependent scheduling, where the processing time of a job depends on its starting time (for a good review see [2]) and position-dependent scheduling, where the processing time of a job depends on its position in a schedule (for a survey see [1]). Themajority of papers on scheduling problems with variable processing times en- tail two limitations. First, the results are mainly connected to scheduling on one machine (see, e.g., [7]) or on parallel machines but with empty precedence con- straints among jobs (see, e.g., [5]). Second, the most of results related to schedul- ing problems with variable job processing times concern particular cases, not gen- eral ones. Examples of recent general results are presented in [3]. 2 Problem formulation The group of problems to be presented during the talk can be formulated as fol- lows. We are given a number of parallel identicalmachines andnnon-preemptable jobs with some precedence constraints. Job processing times are variable and depend on the position r of a job in a schedule. This dependency is described by a positive and non-increasing discrete function φ of argument r. In other words, the processing time of the j-th job on r-th position in a schedule is equal to pj,r = φ(r), where 1 ≤ r, j ≤ n. The aim is to find a schedule with minimal max- imum completion time or minimal total weighted completion time. Using the commonly known scheduling notation (for a brief description see [2]), we denote these problems by P|prec, pj,r = φ(r)|f, where f ∈ {Cmax, ∑ wiCi}. * Speaker, email: bap@amu.edu.pl 65 Special cases of these problems, when φ(r) = 1 for every r, are the problems of scheduling jobs with unit job processing times, P|prec, pj,r = 1|f. Therefore, a natural question is whether some known algorithms for the latter problem can be applied to their counterparts with job processing times described by the φ function. We give an answer to this question applying a new methodology of transforming schedules. We also specify certain conditions, under which the P|prec, pj,r = φ(r)|f problems can be solved by appropriately modified algorithms for unit job processing times. 3 Our results Let φ : N+ → Q+ be any discrete function satisfying the condition φ(r) > 0 for every r ∈ N+, where N+ = N \ {0}. Moreover, let Φ be a function defined as Φ(k) = ∑k i=1 φ(i), where k ∈ N. Notice that Φ(0) = 0 and that the Φ function is a bijection between its domain and image. A schedule of n jobs is called a φ-natural schedule, if there is at least one job, such that the starting time of this job is equal to 0 and for every job both its starting and its completion time are the values of the Φ function at some points. If every job started at time Φ(k) is completed at time Φ(k+ 1), then the schedule is called a φ-simple schedule. If φ(r) = 1 for every r, then every φ-natural schedule is called a a natural schedule and, consequently, every φ-simple schedule is called a simple schedule. Notice, that every simple schedule is a schedule of jobs with unit processing times. A schedule is called a continuous schedule, if every machine starts the processing of jobs at the moment 0 and none of the machines is idle before finishing all the jobs assigned to it. Lemma1. Let there be given a number of identical parallel machines able to execute each of available jobs. If an algorithm A generates a continuous simple schedule for job processing times in the form of pj,r = 1, then algorithmA generates a continuous φ-simple schedule for job processing times in the form of pj,r = φ(r). The above lemma is used in proofs of the following theorems. Theorem 2. Let φ be a positive non-increasing discrete function and let I be arbi- trary instance of the P|prec, pj,r = 1|f problem, where f ∈ {Cmax, ∑ wiCi, ∑ Ci}. If algorithm A generates an optimal schedule for I and it is a continuous simple schedule, then algorithm A generates also an optimal schedule for the correspond- ing instance of the P|prec, pj,r = φ(r)|f problem and it is a continuous φ-simple schedule. Theorem 3. If the φ function is positive and non-increasing with respect to r, then Hu’s algorithm [4] solves the P|in-tree, pj,r = φ(r)|Cmax problem. 66 The First International Workshop on Dynamic Scheduling Problems We will present and comment several examples of applications of the above the- orems. Moreover, we will present some examples showing that the assumptions of our theorems are reasonably strong. In particular, we will show some counter- examples to several hypotheses, where the assumptions are weakened. 4 Future research The results can be a base for further research on the problem of applying known algorithms tomore general cases. It is an open question, whetherwe can construct transformations such as presented here for other classes of schedules. References [1] D. Biskup, A state-of-the-art review on scheduling with learning effects, European Journal of Operational Research, 188 (2008), 315–329. [2] S. Gawiejnowicz, Time-Dependent Scheduling, Springer, Berlin-Heidelberg, 2008. [3] S. Gawiejnowicz, A. Kononov, Isomorphic scheduling problems, Annals of Operations Research, 213 (2014), 131–145. [4] T-C. Hu, Parallel sequencing and assembly line problems, Operations Research, 9 (1961), 841–848. [5] G. Mosheiov, Minimizing total absolute deviation of job completion times: Extensions to position-dependent processing times and parallel identical machines, Journal of the Operational Research Society, 59 (2008), 1422–1424. [6] B. Przybylski, Precedence constrained parallel-machine scheduling of posi- tion-dependent jobs, submitted. [7] J-B. Wang, J-J. Wang, Single-machine scheduling problems with precedence constraints and simple linear deterioration, Applied Mathematical Modelling, 39 (2014), 1172–1182. June 30 – July 1, 2016, Poznań, Poland 67 Single machine scheduling subject to a generalized linear cumulative effect Kabir Rustogi University of Greenwich, London, United Kingdom Vitaly A. Strusevich* University of Greenwich, London, United Kingdom Keywords: single machine, maintenance, approximation schemes, half-product 1 Introduction This talk is devoted to a single machine scheduling model, in which actual pro- cessing times of the jobs are not constant but are subject to a special effect. Each job j ∈ N = {1, 2, . . . , n} is associated with an integer pj that is called its ”normal” processing time. This value can be understood as the actual processing duration of job j, provided that the machine is in some initial state, and may change due to a certain effect that extends a traditional cumulative effect. Under the cumulative effect the actual processing time of job j depends on pj and on the sum of normal processing times of all jobs sequenced earlier; see, e.g., [6]. In our model, the ac- tual processing time of a job depends on the sum of certain parameters, other than normal processing times, associated with previously scheduled jobs. For the introduced model, we solve the problem of minimizing the makespan, with and without precedence constraints. We also consider a situation when a m